[LeetCode] 143. Reorder List

Problem : https://leetcode.com/problems/reorder-list/

Construct the needed list by doing preorder and postorder traversal at the same time.

Time Complexity = O ( N )

Space Complexity =  O ( 1 ) 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
        self.dummy = ListNode()
        self.p = self.dummy
        
        self.preorder = head
        self.seen = set()
        
        def postorder(node):
            if node:
                postorder(node.next)
                
                # add node by preorder traversal
                if self.preorder not in self.seen:
                    self.seen.add(self.preorder)
                    
                    self.p.next = self.preorder
                    self.preorder = self.preorder.next

                    self.p = self.p.next
                
                # add node by postorder traversal
                if node not in self.seen:
                    self.seen.add(node)
                    
                    self.p.next = node
                    self.p = self.p.next
        
        postorder(head)
        
		# end the list
        self.p.next = None

A stack based solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head: return
        
        stack = []
        
        p = head
        total = 0
        
        while p:
            stack.append(p)
            p = p.next
            total += 1
        
        total = total // 2
        
        p = head
        while total > 0:
            tmp = p.next
            p.next = stack.pop()
            total -= 1
            
            p = p.next
            p.next = tmp
            p = p.next
            
        
        p.next = None

An iterative solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode p1 = head;  // slow
        ListNode p2 = head;  // fast
        
        // find the middle node
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        
        ListNode mid = p1.next;
        p1.next = null;
        
        // return directly if the second half list is empty
        if (mid == null) {
            return;
        }
        
        // reverse the second half list
        ListNode pre = null;
        ListNode cur = mid;
        
        while (cur.next != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        cur.next = pre;
        
        // reorder the list
        p1 = head;
        p2 = cur;
        
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        
        while (p1 != null || p2 != null) {
            
            if (p1 != null) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }
            
            if (p2 != null) {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
    }
}

Edited on 12/21/2021. Add the iterative solution.