Reorder List - Leetcode Solution

Problem Statement:

Given the head of a singly linked list, reorder it to a new list where each node in the new list is alternatively from the beginning and end of the original list.

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

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

Solution:

To solve this problem, we can divide it into three main parts:

1. Splitting the list into two halves
2. Reversing the second half of the list
3. Combining the two halves of the list

Let's go through each of these parts in detail:

1. Splitting the list into two halves

We can use the fast-and-slow pointer technique to split the linked list into two halves. Essentially, we start two pointers, one that moves one step at a time (slow pointer) and the other that moves two steps at a time (fast pointer). Eventually, when the fast pointer reaches the end of the list, the slow pointer will be at the midpoint of the list.

2. Reversing the second half of the list

After we have split the list into two halves (say, left and right), we need to reverse the second half (right half). To do this, we can again use the fast-and-slow pointer technique, but this time we start from the midpoint of the list (where the slow pointer is). We use the fast pointer to keep track of the previous node, and the slow pointer to keep track of the current node. At each step, we make the current node point to the previous node, and move both pointers one step forward. We continue until the slow pointer reaches the end of the list.

3. Combining the two halves of the list

Once we have both halves of the list, we can combine them by alternately picking one node from each half until we reach the end of both halves. If one half is longer than the other, we simply append the remaining nodes to the end of the new list.

Here's the Python implementation of the above approach:

class Solution: def reorderList(self, head: ListNode) -> None: if not head: return

    # step 1: split the list into two halves
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    left, right = head, slow.next
    slow.next = None
    
    # step 2: reverse the second half of the list
    prev, curr = None, right
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    right = prev
    
    # step 3: combine the two halves of the list
    while right:
        nxt1, nxt2 = left.next, right.next
        left.next = right
        right.next = nxt1
        left, right = nxt1, nxt2
        
    return head

Time Complexity: O(n), where n is the number of nodes in the linked list. Space Complexity: O(1), since we are reusing the existing nodes in the linked list.

1