Reorder Linked List

Problem

You are given the head of a singly linked-list.

The positions of a linked list of length = 7 for example, can intially be represented as:

[0, 1, 2, 3, 4, 5, 6]

Reorder the nodes of the linked list to be in the following order:

[0, 6, 1, 5, 2, 4, 3]

Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify the values in the list’s nodes, but instead you must reorder the nodes themselves.

Examples

Example 1:

Input: head = [2,4,6,8]

Output: [2,8,4,6]

Example 2:

Input: head = [2,4,6,8,10]

Output: [2,10,4,8,6]

Constraints

• 1 <= Length of the list <= 1000.
• 1 <= Node.val <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.

Solution

We need to split the linked list in half, reverse the lower half, then merge in sync the first half and second half. We can use fast/slow pointer to find the end of the first half, then increment once more to start at 2nd half. Then reverse the 2nd half, and merge.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *slow = head;
        ListNode* fast = head;
        // Walk using slow/fast point
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // Slow ends at end of first half
        // We want to reverse the 2nd half (everything right of slow)
        ListNode *current = slow->next;
        ListNode *prev = nullptr;
        slow->next = nullptr;   // Cuts off 1st half from 2nd half
        while (current) {
            ListNode* tmp = current;
            current = current->next;
            tmp->next = prev;
            prev = tmp;
        }
 
        // Merge, left -> right -> left.next
        ListNode *left = head;
        ListNode *right = prev;
        while (right) {
            ListNode *tmp1 = left->next;
            ListNode *tmp2 = right->next;
            left->next = right;
            right->next = tmp1;
            left = tmp1;
            right = tmp2;
        }
    }
};