Leetcode 143. Reorder List

Problem

Leetcode 143 - Reorder List

Example:

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

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

Approach

First, we find a mid point of the linked list using the fast and slow technique.

Second, we reverse the later half point so we have 2 seperate linked list (1,2,3), (5,4)

Third, we connect first and second linked list alternatively

Visualization of the Approach:

First, we find a mid point of the linked list using the fast and slow technique
1 -> 2 -> 3 -> 4 -> 5
s
f

1 -> 2 -> 3 -> 4 -> 5
     s
          f

1 -> 2 -> 3 -> 4 -> 5
          s
                    f
Thus, our mid point is at s (3)

Second, we reverse the later half point so we have 2 separate linked list
1 -> 2 -> 3   4 -> 5

1 -> 2 -> 3   4 <- 5

Third, we alterntively merge linked list
1 -> 2 -> 3   4 <- 5
f                  s

1 -> 5 -> 2 -> 3   4
          f        s

1 -> 5 -> 2 -> 4 -> 3
                    f

Since second doesn't exist, we return

Here is the Python code for the solution:

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # finding mid point of linked list
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # reversing the later half and separate into 2 list
        prev, curr = None, slow.next
        slow.next = None
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        
        # merge the 2 list alternatively
        first, second = head, prev
        while second:
            temp_f, temp_s = first.next, second.next
            
            first.next = second
            second.next = temp_f

            first = temp_f
            second = temp_s    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$