Learning Journal

2/26/2024

Reorder List

Tags: algorithms leetcode recursion linked_list

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
    if(head === null) return;

    let cur = head;
    let done = false;

    traverse(head);

    function traverse(node:ListNode) {
        if(node.next !== null)
            traverse(node.next);
        
        if(done) return;
        
        if(node === cur.next || node === cur) {
            node.next = null;
            done = true;
            return;
        }
        else {
            const next = cur.next;
            cur.next = node;      
            node.next = next;
            cur = next;
        }

    }
};/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
    if(head === null) return;

    let cur = head;
    let done = false;

    traverse(head);

    function traverse(node:ListNode) {
        if(node.next !== null)
            traverse(node.next);
        
        if(done) return;
        
        if(node === cur.next || node === cur) {
            node.next = null;
            done = true;
            return;
        }
        else {
            const next = cur.next;
            cur.next = node;      
            node.next = next;
            cur = next;
        }

    }
};

PROBLEM

The solution on Leetcode has 3 steps: divide the list into 2 halves, reverse the second half, then merge two list alternately.

My solution is kind of a improvement from it by instead of divide the list into 2 halves and reverse the second half, I just use recursion to go to the end of the list, then connect one by one each element at the end with each element at the beginning. The catch is you need to stop in the middle. I use a boolean variable done to take care of that.

Revised by ChatGPT

The standard solution on LeetCode for the "Reorder List" problem involves three steps: dividing the list into two halves, reversing the second half, and then merging the two halves alternately. My solution takes a different approach by utilizing recursion to directly connect the end nodes with the start nodes, effectively eliminating the need to split and reverse the list.

The recursion goes all the way to the end of the list, and on its way back, it rearranges the nodes by connecting each end node with its corresponding start node. To ensure that the rearrangement stops at the middle of the list, I use a boolean variable done. Once the middle is reached, done is set to true, which halts any further modifications to the list structure.

This approach simplifies the process by avoiding the explicit division and reversal of the list, while still achieving the desired reordering. However, it's important to note that his solution has a space complexity of O(n) due to the recursive call stack, which is a trade-off for the reduced complexity in list manipulation,