143. Reorder List

Problem Description

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]

Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]

Output: [1,5,2,4,3]

Problem Link

Approach 1

We can use dequeue data structure to solve this problem. In deque data structure we can take a node/value from both the front and end of the queue.

1. First, we will create a deque and then traverse the linked list and push the nodes inside the deque.

ListNode* temp = head;
deque<ListNode*> reorder;

while(temp != nullptr){
    reorder.push_back(temp);
    temp = temp->next;
}

2. Now, before traversing over the deque, first, we will take the front node from the deque and insert it to the temp variable.

temp = reorder.front();
temp->next = nullptr;
reorder.pop_front();

3. Then we can start popping the nodes from the deque and connect them accordingly. First the back node, and then the front node, in this sequence.

while(!reorder.empty()){
    if(!reorder.empty()){
        ListNode* node = reorder.back();
        node->next = nullptr;
        temp->next = node;
        temp = temp->next;
        reorder.pop_back();
    }
    if(!reorder.empty()){
        ListNode* node = reorder.front();
        node->next = nullptr;
        temp->next = node;
        temp = temp->next;
        reorder.pop_front();
    }
}

Caution:

Before connecting the nodes, make sure that you have set the next of the current node to nullptr. Because when you will write temp = temp->next, if you do not set the next of that node to nullptr, it will point to the node of the original array.

Example:

[1->2->3->4->5]

After the first iteration of the while loop: [1->5->2]

What happens if we don't set the node->next=nullptr? let's dry run the code:

Connecting node 2:

node = 2
temp->next = node (5->next = 2)
temp = temp->next (temp = 5->next = 2)

`the problem arise here, because as we did not set the next pointer of the node 2 to nullptr, it is still pointing to the older list (2->next = 3)`

Solution 1:

TC:O(n) SC:O(n)

/**
 * 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* temp = head;
        deque<ListNode*> reorder;

        while(temp != nullptr){
            reorder.push_back(temp);
            temp = temp->next;
        }
        temp = reorder.front();
        temp->next = nullptr;
        reorder.pop_front();

        while(!reorder.empty()){
            if(!reorder.empty()){
                ListNode* node = reorder.back();
                node->next = nullptr;
                temp->next = node;
                temp = temp->next;
                reorder.pop_back();
            }
            if(!reorder.empty()){
                ListNode* node = reorder.front();
                node->next = nullptr;
                temp->next = node;
                temp = temp->next;
                reorder.pop_front();
            }
        }
    }
};