LeetCode Reorder List: Linear Time and Constant Space

Overview

The LeetCode Reorder List problem could be solved in linear time and using constant space with the key to split the list into half and reverse second half.

LeetCode Reorder List Problem

Given a singly linked list L: LL1→…→Ln-1Ln,
reorder it to: LLnL1Ln-1L2Ln-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}.

Solution with Linear time and Constant Space

(1) O(N^2) time and O(1) Space

The rule to reorder list is not hard to figure out, for the linked list like this A->B->…->C->T->NULL, starting from the original input linked list, cut the tail T off and insert this tail node T between the head A and B, so it becomes A->T->B->…C->NULL, for the remaining linked list starting from B (could be treated as the new head for the remaining linked list), we do the same thing again, that is, cut C off, and insert after B, and we continue this process until there is not such tail nodes to process. Without any extra information gained from pre-processing (like the split and reverse we will discuss later on), we have to get access to the NEW tail node on the fly each time by scanning the remaining linked list, so the time complexity becomes O(N^2), this approach woould get TLE and thus won’t be able to pass the LeetCode OJ

(2) O(N) time and O(N) space

What is the problem of the first approach? The problem with it scans the remaining linked list repeatedly, and thus make the time complexity 1 + 2 + 3 + … n = O(N^2), the purpose of this scanning is just to get the pointer to the tail node of the remaining linked list, so what about using an array to keep all these information? Yes, why not! So we need an extra array to keep the pointers for each node, so we can identify the tail node in constant time by accessing the extra array directly, so when we need to process the remaining linked list, we just get the tail node from the array in O(1) time which would be inserted after the new head of the remaining linked list. This shows the tradeoff between time and space cost.

(3) Furthermore, can we come up with even more improvement to make the space cost O(1)? Yes, we can! Think about the second approach again: we actually only need half the original linked list to do insertion and we access the tail node in an reversed order! So here comes the optimal solution: Firstly, we need to find the second half of List  (could use slow and fast pointer) ; secondly, we split the linked into the first and second half, reverse the second hafl , and make the end of first half point to NULL; Finally, we do insert each node of the reversed second half into the first half of List by the insertion rule described in the problem.

Here is an example: If we have 0-> 1 -> 2 – >3 -> 4 -> 5 -> NULL, reverse 4 -> 5 to 5 -> 4, make the first half end to NULL, so we have two split linked list: 0 -> 1 -> 2 – >3 -> NULL and 5 -> 4 -> NULL, Insert each of second list node into the first list between current and next node and finally we would have the reordered list 0 -> 5 -> 1 – > 4 – >2 – > 3 -> NULL. The following code implemented this optimal solution and is accepted by the LeetCode OJ to pass this Reorder List problem:

class Solution {
public:

ListNode *newSecond;
ListNode *newHead;

ListNode *reverse(ListNode *head) {
    if (NULL == head || NULL == head->next) return head;
    ListNode *nextHead = head->next;
    ListNode *currNode = head->next;
    head->next = NULL;
    while (currNode) {
        nextHead = currNode->next;
        currNode->next = head;
        head = currNode;
        currNode = nextHead;
    }
    return head;
}

void reorderListInner(ListNode *head, ListNode *second) {
    if (NULL == head || NULL == head->next)
        return ;
    if (NULL == second)
        return ;

    newHead = head->next;
    newSecond = second->next;
    second->next = head->next;
    head->next = second;
    reorderListInner(newHead, newSecond);
}

void reorderList(ListNode *head) {
    if (NULL == head || NULL == head->next)
        return ;

    ListNode *slow = head;
    ListNode *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *secondLinkedList = reverse(slow->next);
    slow->next = NULL;
    reorderListInner(head, secondLinkedList);
}

};

Summary

The LeetCode Reorder List problem could be solved in linear time and using constant space with the key to split the list into half and reverse second half.

Written on November 23, 2014