LeetCode: 143 Reorder List

Problem Description:

You are given the head of a singly linked list. You need to reorder the list to follow the pattern:

• L0 → L1 → L2 → … → Ln-1 → Ln
• becomes L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

You must do this in-place without altering the nodes’ values.

Example 1:

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

Example 2:

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

Original Code:

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head:
            return head  # If the list is empty, return

        slow, fast = head, head.next  # Initialize slow and fast pointers

        # Find the middle of the list
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        cur = slow.next  # Start from the second half of the list
        pre = slow.next = None  # Split the list into two halves

        # Reverse the second half of the list
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        l1, l2 = head, pre  # Initialize two pointers for the two halves

        # Merge the two halves
        while l2:
            tp1, tp2 = l1.next, l2.next  # Store the next nodes
            l1.next = l2  # Link the first half to the second half
            l2.next = tp1  # Link the second half back to the first half
            l1, l2 = tp1, tp2  # Move to the next nodes

Line-by-Line Explanation and Example Execution:

1. def reorderList(self, head: Optional[ListNode]) -> None:

   • Defines the function reorderList, which takes the head of a linked list and modifies it in-place.

2. if not head:

   • Checks if the list is empty. If so, it returns immediately.

3. slow, fast = head, head.next

   • Initializes two pointers: slow (for finding the middle) and fast (to traverse at double speed).

4. Finding the Middle:

   • while fast and fast.next:
     • This loop finds the middle of the list using the slow and fast pointer technique.
     • When fast reaches the end, slow will be at the middle of the list.

5. Splitting the List:

   • cur = slow.next
     • Sets cur to the start of the second half of the list.
   • pre = slow.next = None
     • Disconnects the first half from the second half by setting slow.next to None.

6. Reversing the Second Half:

   • while cur:
     • This loop reverses the second half of the list.
   • nxt = cur.next
     • Stores the next node.
   • cur.next = pre
     • Reverses the link.
   • pre = cur
     • Moves pre to the current node.
   • cur = nxt
     • Moves to the next node.

7. Merging Two Halves:

   • l1, l2 = head, pre
     • Initializes two pointers to the start of the first half and the reversed second half.
   • while l2:
     • Merges the two halves together:
     • tp1, tp2 = l1.next, l2.next
       • Stores the next nodes.
     • l1.next = l2
       • Links the first half to the second half.
     • l2.next = tp1
       • Links the second half back to the first half.
     • l1, l2 = tp1, tp2
       • Moves to the next nodes.

Example Execution:

Assuming we have the following linked list:

head = 1 -> 2 -> 3 -> 4 -> 5 -> None

Execution steps:

1. Finding the Middle:

   • slow = 3, fast = None (loop stops).
   • The list is split into two halves: 1 -> 2 -> 3 and 4 -> 5.

2. Reversing the Second Half:

   • Start with cur = 4.
   • Reverse the second half:
     • 5 -> 4 -> None.

3. Merging the Two Halves:

   • l1 = 1, l2 = 5.
   • Merging:
     • 1 -> 5, then 2 -> 4, then 3 -> None.

4. Final Result:

   • The reordered list is 1 -> 5 -> 2 -> 4 -> 3 -> None.

Time Complexity Analysis:

• 时间复杂度：O(n)
  • 其中 n 是链表中的节点数量。每个节点仅被处理一次。

Space Complexity Analysis:

• 空间复杂度：O(1)
  • 只使用固定数量的指针，不依赖于输入链表的大小。

Tips and Warnings:

1. Basic Cases:

   • Always handle basic cases (like empty lists or single-node lists) to avoid errors.

2. Understanding Pointers:

   • Ensure a solid understanding of how linked list pointers work, especially when reversing and merging lists.

Summary

• Iterative Method: 使用迭代有效地反转链表，时间复杂度为 O(n)，空间复杂度为 O(1)。
• 清晰易懂：代码简单明了，易于理解，适合处理此类问题。

Application Tips

1. 选择合适的方法：

   • 根据具体问题选择最合适的方法，以确保算法的效率和可读性。

2. 处理边界情况：

   • 在算法设计中，始终考虑处理输入数据的边界情况。

3. 优化空间使用：

   • 在处理大数据时，考虑使用更节省空间的算法。