Reorder List

This problem is a combination of these three easy problems:

Middle of the Linked List.
Reverse Linked List.
Merge Two Sorted Lists.

You can reorder a linked list as described by performing the following steps:

Find the Middle of the List: Use the slow and fast pointer technique to find the middle of the list.
Reverse the Second Half: Reverse the second half of the list.
Merge the Two Halves: Merge the first half and the reversed second half alternately.

Here’s a Python function to accomplish this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return 

        # find the middle of linked list [Problem 876]
        # in 1->2->3->4->5->6 find 4 
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next 

        # reverse the second part of the list [Problem 206]
        # convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4
        # reverse the second half in-place
        previous = None 
        current = slow
        while current:
            current.next, previous, current = previous, current, current.next       

        # merge two sorted linked lists [Problem 21]
        # merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4
        first, second = head, previous
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next

Explanation

Step 1: Find the middle of the list using the slow and fast pointer method.
Step 2: Reverse the second half of the list by changing the pointers.
Step 3: Merge the original first half and the reversed second half by rearranging the pointers.

Key Takeaway

This approach reorders the linked list without modifying the values in the nodes, satisfying the constraints. By splitting, reversing, and merging, the list is reordered in-place as required.

=begin

Define the Terms

Define the Interface Input: head Output: nothing

Analyze the Input and Output

Initial State | What is the next state? | What is the state before the penultimate state? | What is the penultimate state? Final State

Remove existing constraints and think freely. Sometimes this simplifies the problem and you can make some progress.

What if we don’t have any constraints? Traversing from forward and backward and joining it.

Work backwards from the result.

What is the step before the final state?

Identify the Invariants

Identify the constraints

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand

[1,2,3,4]

[1,4] - First connects to the last [2,3] - Second connects to the element before last

[1,4] -> [2,3]

[1,2,3,4,5] [1,5] [2,4] [3]

[1,5] -> [2,4]

[1,5] -> [2,4] -> [3]

We split the list by half Reverse the second half [4, 3] [1,2] [4,3]

1 -> 4 -> 2 -> 3

If you have odd number of elements in the linked list the middle element will to the last.

[1,2,3,4,5] We need to split this list by half. Do we need to make the middle element part of the first list or the second list.

[1,2] [3,4,5] - Split [1,2] [5, 4, 3] - Reverse second half [1,5] [2, 4, 3] - 1 connects to 5, 2 connects to 4 [1, 5] -> [2,4,3] - Merge first list with the second list [1,5,2,4,3]

[1,2, 3] [4,5] - Split [1,2, 3] [5, 4] - Reverse second half [1,2,3] [5,4] - 1 connects to 5, 2 connects to 4 [1, 5, 3] -> [2,4] - Merge first list with the second list [1,5,3,2,4]

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach

Analyze Time and Space Complexity

Time: O(N) Space: O(1)

Outline the Solution - Split the list by half - If you have odd number of elements, add the middle element to the first list - Reverse the second half - Alternate linking the elements in the both the linked lists.

Key Takeaways

Problem decomposition
```
      v          
```

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

=end

Definition for singly-linked list.

class ListNode

attr_accessor :val, :next

def initialize(val = 0, _next = nil)

@val = val

@next = _next

end

@param {ListNode} head

@return {Void} Do not return anything, modify head in-place instead.

def reorder_list(head) slow = head fast = head

while !fast.nil? && !fast.next.nil? slow = slow.next fast = fast.next.next end

previous = nil current = slow

while !current.nil?

save the link of the next node of the current

 tmp = current.next

Reverse the link

 current.next = previous

move follower and leader by one

 previous = current
 current = tmp

end

1 -> 2 4 -> 3

head, slow

first = head

???

second = previous

while !second.next.nil?
   tmp = first.next
    first.next = second
    first = tmp
    
    tmp = second.next

linking the end

    second.next = first
    second = tmp
end

end