328. Odd Even Linked List 

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
class Solution {
    public ListNode oddEvenList(ListNode head) {
        // 注意此处并未连接两个 dummy 节点且这两个节点未与 head 节点建立连接
        ListNode dummyOddHead = new ListNode();
        ListNode dummyEvenHead = new ListNode();
        ListNode curr = head;

        ListNode preOdd = dummyOddHead, preEven = dummyEvenHead;
        while (curr != null) {
            ListNode odd = curr;
            ListNode even = curr.next; // even can be null

            preOdd.next = odd;
            preEven.next = even;

            preOdd = odd;
            preEven = even;

            curr = even == null ? null : even.next;
        }

        preOdd.next = dummyEvenHead.next; // 不要忘记连接两个子链表

        return dummyOddHead.next;
    }
}

References

328. Odd Even Linked List