LeetCode(LinkedList)Odd Even LinkedList

2018-06-22

Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

1 2	Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULL

Example 2:

1 2	Input: 2->1->3->5->6->4->7->NULL Output: 2->3->6->7->1->5->4->NULL

Note:

The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …

思路：采用了删除偶结点，并将删除掉的偶结点存储在一个ArrayList中，然后重新赋予偶结点前后关系，再将排列好的偶结点插入已经完成删除操作的奇结点序列最后即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
   public ListNode oddEvenList(ListNode head) {
    	  if(head==null){
              return head;
          }
          if(head.next==null){
              return head;
          }
          ListNode podd=head;
          ListNode peven=head.next;
          
          helper(podd);
          //为所有的偶结点重新赋予前后关系
          int len=listeven.size();
          for(int i=0;i<len-1;i++) {
        	  listeven.get(i).next=listeven.get(i+1);
          }
          
          
          ListNode temp=podd;
          while(temp.next!=null){
              temp=temp.next;
          }
          temp.next=listeven.get(0);
          return podd;
        
    }
    ArrayList<ListNode> listeven=new ArrayList<ListNode>();
    public void helper(ListNode head){
    	if(head==null) {
    		return;
    	}
        if(head.next!=null){
            ListNode temp=head.next;
            head.next=temp.next;
            //消除偶结点的next指向
            temp.next=null;
            listeven.add(temp);
            helper(head.next);
        }
    }
}