Reorder List

class Solution {
public:
    void reorderList(ListNode* head_node) {
        if (!head_node) return;
        
        // Find the middle node of the linked list
        ListNode* middle_slow = head_node;
        ListNode* runner_fast = head_node;
        while (runner_fast && runner_fast->next) {
            middle_slow = middle_slow->next;
            runner_fast = runner_fast->next->next;
        }
        
        // Reverse the second half of the list
        ListNode* previous_node = NULL;
        ListNode* current_node = middle_slow;
        ListNode* hold_next;
        while (current_node) {
            hold_next = current_node->next;
            current_node->next = previous_node;
            previous_node = current_node;
            current_node = hold_next;
        }
        
        // Merge the first half and the reversed second half
        ListNode* first_half = head_node;
        ListNode* second_half = previous_node;
        while (second_half->next) {
            hold_next = first_half->next;
            first_half->next = second_half;
            first_half = hold_next;

            hold_next = second_half->next;
            second_half->next = first_half;
            second_half = hold_next;
        }
    }
};

The given solution in C++ addresses the problem of reordering a linked list such that the elements are rearranged from the ends towards the center. Specifically, it interlaces the nodes starting from the first and the last, moving towards the middle. Here's the process broken down:

• Initial Check: Initially, the function checks if the passed head node, head_node, is NULL. If it's NULL, the function returns immediately as there's no list to reorder.

• Find the Middle Node: Using the slow and fast pointer technique, it locates the middle of the list. The slow pointer, middle_slow, moves one step at a time, while the fast pointer, runner_fast, moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

• Reverse the Second Half: Starting from the middle node identified by middle_slow, the second half of the list is reversed. The pointers previous_node, current_node, and hold_next assist in performing the reversal in-place.

• Merge the Halves: Once the second half is reversed, the list consists of two parts: the first half starting from head_node to the middle, and the second half starting from the node just before the NULL (previously the last node of the list). The two halves are then merged alternately. This is done using a loop wherein the nodes from each part are linked alternately until all nodes from the second half are correctly positioned.

This method effectively reorders the list without using extra space for an auxiliary data structure, making it efficient in terms of space complexity. The use of multiple pointers to handle the nodes directly manipulates the links within the list, ensuring that the order is adjusted in-place.

class Solution {
    public void rearrangeList(ListNode headNode) {
        if (headNode == null) return;

        ListNode slowPtr = headNode, fastPtr = headNode;
        while (fastPtr != null && fastPtr.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }

        ListNode previous = null, current = slowPtr, tempNode;
        while (current != null) {
            tempNode = current.next;

            current.next = previous;
            previous = current;
            current = tempNode;
        }

        ListNode leftHalf = headNode, rightHalf = previous;
        while (rightHalf.next != null) {
            tempNode = leftHalf.next;
            leftHalf.next = rightHalf;
            leftHalf = tempNode;

            tempNode = rightHalf.next;
            rightHalf.next = leftHalf;
            rightHalf = tempNode;
        }
    }
}

The provided Java program focuses on restructuring a singly linked list using a specific strategy. Starting with a function called rearrangeList which takes the head node of the linked list as its argument, the solution follows these steps:

1. First, it ensures that the provided list is not empty by checking if the headNode is null. If it is, the function returns immediately, doing nothing.
2. The approach uses two pointers, slowPtr and fastPtr, both initialized to the head of the list. These pointers help in finding the middle of the list. slowPtr moves one node at a time, while fastPtr moves two nodes at a time, reaching the end of the list quicker. When fastPtr can no longer move two steps forward, slowPtr is essentially at the midpoint of the list.
3. To reverse the second half of the list, the program sets up a while loop starting from the node right after slowPtr. The loop uses three pointers: previous, current, and tempNode. It reverses the links between the nodes until current reaches the list's end.
4. After reversing, the program merges the two halves of the list. leftHalf starts from the beginning with the head node, and rightHalf starts from the previous node created in the reversal step, representing the last node in the reversed half. The merging occurs in another loop, alternating nodes from both halves until all the nodes from the second half are correctly interleaved with the first half.

By following this procedure, the list is reordered without using additional data structures, effectively utilizing the linked list properties. This transformation requires careful handling of node pointers to prevent common pitfalls like lost connections or incorrect node linking. This algorithm is efficient with a time complexity of O(n), where n is the number of nodes in the list.

// ListNode structure definition assumed
// struct ListNode {
//   int val;
//   struct ListNode *next;
// };
void rearrangeList(struct ListNode* headNode) {
    if (headNode == NULL) return;
    struct ListNode* slow_ptr = headNode;
    struct ListNode* fast_ptr = headNode;
    while (fast_ptr != NULL && fast_ptr->next != NULL) {
        slow_ptr = slow_ptr->next;
        fast_ptr = fast_ptr->next->next;
    }
    struct ListNode* previous = NULL;
    struct ListNode* current = slow_ptr;
    struct ListNode* temp;
    while (current != NULL) {
        temp = current->next;
        current->next = previous;
        previous = current;
        current = temp;
    }
    struct ListNode* start = headNode;
    struct ListNode* end = previous;
    while (end->next != NULL) {
        temp = start->next;
        start->next = end;
        start = temp;
        temp = end->next;
        end->next = start;
        end = temp;
    }
}

The C function rearrangeList is designed to reorder the nodes of a linked list in such a way that the nodes are arranged starting from the first and last, then second and second last, and so on. The process can be broken down into the steps as follows:

• First, two pointers, slow_ptr and fast_ptr, are used to find the middle of the linked list. The fast_ptr moves two nodes for every one node that slow_ptr moves, so when fast_ptr reaches the end, slow_ptr will be at the middle.
• Next, the second half of the list starting from slow_ptr is reversed. This reversal is accomplished using a simple in-place algorithm where the links between nodes are reversed one by one. This requires three temporary pointers: previous, current, and temp.
• Once the list is reversed from the middle to the end, the reordering starts. The process iterates over the first half and the reversed second half simultaneously, rearranging the pointers so that the first node points to the last, then the second to the second last, and so on.
• This reordering continues until all the nodes from the second half are rearranged.

By following these steps, rearrangeList ensures that the linked list is reordered from both ends towards the middle without the need for additional storage, achieving the reordering in-place with O(n) time complexity and O(1) space complexity.

var reorderLinkedList = function (listHead) {
    if (listHead === null) return;
    let slowPointer = listHead;
    let fastPointer = listHead;
    // Finding the middle point
    while (fastPointer !== null && fastPointer.next !== null) {
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }
    // Reversing the latter half of the list
    let previous = null;
    let current = slowPointer;
    while (current !== null) {
        let nextTemp = current.next;
        current.next = previous;
        previous = current;
        current = nextTemp;
    }
    // Merging the two halves
    let firstHalf = listHead;
    let secondHalf = previous;
    while (secondHalf.next !== null) {
        let temp = firstHalf.next;
        firstHalf.next = secondHalf;
        firstHalf = temp;
        temp = secondHalf.next;
        secondHalf.next = firstHalf;
        secondHalf = temp;
    }
};

This JavaScript function, reorderLinkedList, reorders a linked list in a specific manner. The goal is to modify the list so it starts with the first element, then jumps to the last element, then the second element, and so forth. The solution involves three main steps:

1. Identify the Middle of the Linked List:

   • Initialize two pointers, slowPointer and fastPointer, both set to the listHead.
   • Using a loop, advance the fastPointer twice as fast as the slowPointer. When fastPointer reaches the end of the list, slowPointer will be at the midpoint.

2. Reverse the Second Half of the List:

   • Starting from slowPointer, traverse the second half of the list, reversing the links between nodes.
   • Keep track of the previous node (previous) and use a temporary variable (nextTemp) to avoid losing the rest of the list while adjusting pointers.

3. Merge the Two Halves:

   • Initialize two pointers, firstHalf starting at listHead and secondHalf starting at the last node of the reversed half of the list (obtained from the second step).
   • Alternately link nodes from firstHalf and secondHalf, readjusting their next pointers to interleave nodes from both halves.

This organized approach ensures that the list is reordered in place without requiring additional data structures, optimizing space efficiency. The use of pointers to manipulate links directly avoids the overhead of additional node creation or array conversion. This solution also demonstrates efficient handling of linked list operations, useful in many practical scenarios involving complex data structures.

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return
        
        # Locate middle of the linked list
        slow_ptr = fast_ptr = head
        while fast_ptr and fast_ptr.next:
            slow_ptr = slow_ptr.next
            fast_ptr = fast_ptr.next.next
        
        # Reverse the second part of the list
        previous, current = None, slow_ptr
        while current:
            next_temp = current.next
            current.next = previous
            previous, current = current, next_temp
        
        # Intertwine the elements of the two halves
        first_part, second_part = head, previous
        while second_part.next:
            first_part.next, first_part = second_part, first_part.next
            second_part.next, second_part = first_part, second_part.next

The provided Python script defines a method to reorder a linked list in a specific pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → .... This pattern is achieved by following a series of steps:

1. First, identify the middle of the linked list using a slow-pointer and fast-pointer approach. This involves incrementing the slow pointer by one step and the fast pointer by two steps until the fast pointer reaches the end. This effectively positions the slow pointer at the midpoint of the list.

2. Once the middle is located, the second half of the list is reversed. This involves rearranging the pointers in the list starting from the middle to the end, so the second half will point in the opposite direction.

3. Finally, merge the two halves of the list. Start from the head of the first half and the head of the reversed second half. Alternately link the nodes from each part until the nodes from the second part are exhausted.

Throughout this process, adjust the linked list in place without using additional arrays or data structures, making the solution space-efficient. The intertwining of nodes ensures that the structure of the linked list adheres to the required reordering pattern. The method modifies the list directly and does not return anything, as it operates on the list nodes themselves using pointers.