143. Reorder List

Description

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Idea

At first, I had an idea that store the list in a vector first and then create a new list according to the rules. But it needs extra space and it’s not in place. Then I found another in place and constant space solution.

1. cut the list at the middle node and make sure the left part’s size is the same as the right part’s or just has one more node.
2. reverse the right part list
3. merge the two llists

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !(head->next)) {
            return;
        }
        ListNode *p1 = head, *p2 = head->next;
        
        // find the middle node
        while (p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        }
        
        // reverse the last middle
        ListNode *a = p1->next;
        while (a && a->next) {
            ListNode *tmp = a->next;
            a->next = tmp->next;
            tmp->next = p1->next;
            p1->next = tmp;
        }
        
        ListNode *head2 = p1->next;
        p1->next = NULL;
        
        // merge the two lists
        ListNode *p = head;
        while (head2) {
            ListNode *tmp1 = p->next;
            ListNode *tmp2 = head2->next;
            p->next = head2;
            head2->next = tmp1;
            p = tmp1;
            head2 = tmp2;
        }
    }
};