LeetCode #143: Reorder List

LeetCode Solutions

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

The “Reorder List” problem on LeetCode asks us to take a singly linked list and reorder it to have the following pattern: the first node is followed by the last node, the second node is followed by the second to last node, and so on.

We can solve this problem in Python 3 by following these steps:

  1. We start by finding the middle of the linked list using the slow and fast pointer approach. This step is important as it helps us divide the linked list into two halves.
  2. We then reverse the second half of the linked list.
  3. Next, we merge the two halves of the linked list. We do this by iterating through both halves and alternately selecting one node from each half and appending it to the new linked list.
  4. Finally, we return the reordered linked list.

Here’s the Python 3 code that implements this approach:

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # Finding the middle of the linked list
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        # Reversing the second half of the linked list
        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        
        # Merging the two halves of the linked list
        first, second = head, prev
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next

In this code, we first find the middle of the linked list using the slow and fast pointer approach. We then reverse the second half of the linked list by iterating through it and reversing the direction of the pointers.

Finally, we merge the first and second halves of the linked list by iterating through both halves and alternately selecting one node from each half and appending it to the new linked list.

Time and Space Complexity

The time complexity of this approach is O(n), where n is the length of the linked list, because we need to iterate through the linked list twice. The space complexity of this approach is O(1) because we only use a constant amount of extra space to store the pointers.