143. Reorder List

Difficulty: Medium

Frequency: N/A

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

/**
 * 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) return;
        //find the middle
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *middle = slow->next;
        slow->next = NULL;
        //reverse the second half
        ListNode *newHead = middle, *newTail = NULL, *next = NULL;
        while (newHead) {
            next = newHead->next;
            newHead->next = newTail;
            newTail = newHead;
            newHead = next;
        }
        //insert into the first half
        ListNode *curHead = head, *curNewHead = newTail;
        while (curHead) {
            if (curNewHead) {
                next = curNewHead->next;
                curNewHead->next = curHead->next;
                curHead->next = curNewHead;
                curNewHead = next;
                curHead = curHead->next->next;
            } else break;
        }
        return;
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn: