Odd Even Linked List

Question

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.

Solution

我覺得 linkedlist 該掌握的重點是，什麼操作會往下 iterate （因為一旦往下就回不去了）、什麼操作只是單純拿到 node 而不會往下走、什麼是 next。這題要想透的是在：

odd.next = odd.next.next; odd = odd.next;

舉 1->2->3->4->5 來說，第一個操作是把 1->3，而第二個操作是把 odd 從 1 移到 3

public ListNode oddEvenList(ListNode head) {
        if (head != null) {
            ListNode odd = head, even = head.next, evenHead = even;

            while (even != null && even.next != null) {
                odd.next = odd.next.next;
                even.next = even.next.next;
                odd = odd.next;
                even = even.next;
            }

            odd.next = evenHead;
        }
        return head;
    }