Solution
Using stack: O(n) memory
We can store all the node elements (pointers) in a stack and then keep two pointers, one from the beginning and the other the top of the stack (last element initially). Consider an example for this approach:
List: 1->2->3->4
-- Step 1 --
Stack: 4 | 3 | 2 | 1
stack.top() -> 4
Head -> 1
Operation List Variables
temp = head->next 1->2->3->4 temp = 2, stack = 4 | 3 | 2 | 1
head->next = stack.top() 1 2->3->4 temp = 2, stack = 4 | 3 | 2 | 1
|________|
stack.top()->next = temp 1->4->2->3 temp = 2, stack = 4 | 3 | 2 | 1
|_____|
stack.pop() 1->4->2->3 temp = 2, stack = 3 | 2 | 1
|_____|
head = temp
-- Step 2 --
Now, head = 2, head->next = 3 and stack.top() = 3
if (head == top || head->next == top) { // this means that we have reached middle of the list
top->next = NULL; // set 3->next = NULL in above case
return;
}
See the code below and try it with another input, you’ll understand the approach.
void reorderList(ListNode* head) {
ListNode *temp = head;
stack<ListNode*> s;
while (temp) {
s.push(temp);
temp = temp->next;
}
temp = head;
while (!s.empty()) {
ListNode *temp2 = temp->next, *top = s.top();
s.pop();
if (temp == top || temp2 == top) {
top->next = NULL;
return;
}
temp->next = top;
top->next = temp2;
temp = temp2;
}
}
Time complexity: O(n) Space complexity: O(1)
O(1) memory solution
The above solution is efficient in terms of time but not so good in terms of memory used. Consider the three step Java solution by wanqing below:
public void reorderList(ListNode head) {
if(head==null||head.next==null) return;
//Find the middle of the list
ListNode p1=head;
ListNode p2=head;
while(p2.next!=null&&p2.next.next!=null){
p1=p1.next;
p2=p2.next.next;
}
//Reverse the half after middle 1->2->3->4->5->6 to 1->2->3->6->5->4
ListNode preMiddle=p1;
ListNode preCurrent=p1.next;
while(preCurrent.next!=null){
ListNode current=preCurrent.next;
preCurrent.next=current.next;
current.next=preMiddle.next;
preMiddle.next=current;
}
//Start reorder one by one 1->2->3->6->5->4 to 1->6->2->5->3->4
p1=head;
p2=preMiddle.next;
while(p1!=preMiddle){
preMiddle.next=p2.next;
p2.next=p1.next;
p1.next=p2;
p1=p2.next;
p2=preMiddle.next;
}
}
Time complexity: O(n) Space complexity: O(1)