Reorder List Problem


Description

LeetCode Problem 143.

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

1
L_0 -> L_1 -> ... -> L_n - 1 -> L_n

Reorder the list to be on the following form:

1
L_0 -> L_n -> L_1 -> L_n - 1 -> L_2 -> L_n - 2 -> ...

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

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 10^4].
  • 1 <= Node.val <= 1000


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    void reorderList(ListNode* head) {
    	// Edge cases
        if ((!head) || (!head->next) || (!head->next->next)) return; 
        
        stack<ListNode*> my_stack;
        ListNode* ptr = head;
        int size = 0;
        while (ptr != NULL) {
        	// Put all nodes in stack
            my_stack.push(ptr);
            size++;
            ptr = ptr->next;
        }
        
        ListNode* pptr = head;
        for (int j=0; j<size/2; j++) {
        	// Between every two nodes insert the one in the top of the stack
            ListNode *element = my_stack.top();
            my_stack.pop();
            element->next = pptr->next;
            pptr->next = element;
            pptr = pptr->next->next;
        }
        pptr->next = NULL;
    }
};




Related Posts

Middle Of The Linked List Problem

LeetCode 876. Given the head of a singly linked list,...

Linked List Components Problem

LeetCode 817. You are given the head of a linked...

Split Linked List In Parts Problem

LeetCode 725. Given the head of a singly linked list...

All O'One Data Structure Problem

LeetCode 432. Design a data structure to store the strings...

Add Two Numbers II Problem

LeetCode 445. You are given two non-empty linked lists representing...