143. Reorder List

📝 Problem Details

• Title: 143. Reorder List
• Link: https://leetcode.com/problems/reorder-list/
• Difficulty: Medium
• Tags/Categories: Linked-List Stack

💭What Were My Initial Thoughts?

- do a first pass through of the list
	- store each second node in the stack

- second pass through, replacing every second node with the top value in the stack

🤔What Did I Struggle With?

this doesnt exactly work since the insertion of the new node would either just be the value or the reference of its next pointer would be broken 

💡 Explanation of Solution

- first pass through
	- store nodes in a stack
	- keep track of the number of nodes in the list (size)

- second pass through
	- iterate size/2 times
		- pop node from the stack
		- insert it after the current node (newPtr)
		- move newPtr forward by two positions to maintain order

- terminate the list 
	- since we are rearranging the nodes, we need to set `newPtr->next = NULL` at the end to avoid cycles.

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head
        || !head->next
        || !head->next->next) return;
 
        stack<ListNode*> stk;
        ListNode* ptr = head;
        int size = 0;
        
        // insert every node into the stack
        // track the size of the list
        while(ptr != NULL) {
            stk.push(ptr);
            size++;
            ptr = ptr->next;
        }
 
        ListNode* newPtr = head;
 
        for(int j=0; j < size / 2; j++) {
            ListNode* element = stk.top();
            stk.pop();
            element->next = newPtr->next;
            newPtr->next = element;
            newPtr = newPtr->next->next;
        }
 
        newPtr->next = NULL;
    }
};