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:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->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 ...
Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Analysis:
it requests to be in place and O(1) space, that reminds me to adjust the pointers while it moves. since it is singly linked list, it goes towards one directly, so that first impression is first node can points to third node, second node can points to fourth node, so on so forth. Further thought found it only need to points to third, then advance to next, and still continue to jump one and points to third. With that, odd and even nodes are separated. since even list has no head, a head pointer should be defined and points to first node in event list. head is already odd list's head. a tail pointer is used for tracking the last node in odd list so that merging two list is just one operation.

First submission failed due to typed ListNode to NodeList on one line, after correction, it's accepted.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode oddEvenList(ListNode head) { if(head==null||head.next==null)return head; ListNode evenHead = head.next; ListNode oddTail = null; ListNode pointer = head;//head is also odd head int cnt=1; while(pointer!=null&&pointer.next!=null){ ///change p's next to third node, repeat it ListNode tmp = pointer.next;//second pointer.next=tmp.next;//third if(cnt++%2==1) oddTail=(pointer.next==null?pointer:pointer.next); pointer=tmp; } oddTail.next=evenHead; return head; } }

The following solution is from http://buttercola.blogspot.ca/2016/06/leetcode-328-odd-even-linked-list.html It uses odd and even pointers and move them together. I consider it is better solution than mine because the cursor move is easier to understand.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public class Solution { public ListNode oddEvenList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; while (even != null && even.next != null) { odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next; } odd.next = evenHead; return head; } }