Tasks

In-place Reversal of a Linked List

May 2023

Index	Task	Number	Difficulty	Link
1	Reverse Linked List	206	Easy	https://leetcode.com/problems/reverse-linked-list/
2	Reverse Linked List II	92	Medium	https://leetcode.com/problems/reverse-linked-list-ii/
3	Reverse Nodes in Even Length Groups	2074	Medium	https://leetcode.com/problems/reverse-nodes-in-even-length-groups/
4	Rotate List	61	Medium	https://leetcode.com/problems/rotate-list/
5	Swap Nodes in Pairs	24	Medium	https://leetcode.com/problems/swap-nodes-in-pairs/
6	Reverse Linked List III	1368	Medium	https://leetcode.com/problems/reverse-sub-linked-lists/
7	Reorder List	143	Medium	https://leetcode.com/problems/reorder-list/
8	Convert Binary Search Tree to Sorted Doubly Linked List	426	Medium	https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
9	Reverse String	344	Easy	https://leetcode.com/problems/reverse-string/
10	Reverse String II	541	Easy	https://leetcode.com/problems/reverse-string-ii/

// 206. Reverse Linked List

// Time: O(n) | Space: O(1)
var reverseList = function(head) {
    // If no node or 1 node only.
    if (!head?.next) {
        return head;
    }
    let prev = null;
    let next = null;
    let temp = head;
    // Iteerate over the list and change pointeers.
    while (temp) {
        next = temp.next;
        temp.next = prev;
        prev = temp;
        temp = next;
    }
    // Return prev as a new head of the reverted list.
    return prev;
};

// 92. Reverse Linked List II

// Time: O(n) | Space: O(1)
var reverseBetween = function(head, left, right) {
    // No need to revert in this case.
    if (!head?.next || left === right) {
        return head;
    }
    let nodeBeforeRevert = head; 
    let curr = head;
    let i = 1;

    // Go to the left pointer.
    while (i < left) {
        nodeBeforeRevert = curr;
        curr = curr.next;
        i++;
    }

    // Prev will become the head of the reverted list.
    let prev = null;
    let next = null;
    // Remember the node that will become last node of the reverted list.
    let tail = curr;

    // Revert list from i (curr) to right.
    while (i <= right) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        i++;
    }
    // Connect the part before left with the reverted list.
    nodeBeforeRevert.next = prev;

    // Connect reverted list with the rest of the original list.
    tail.next = curr;

    // Return head of the result list.
    return left === 1 ? prev : head; 
};

/*
 * In-place Reversal of a Linked List
 * ----------------------------------
 * 1. Find the left position node.
 * 2. Reverse the list from the left position node to the right position node.
 * 3. Merge the reversed list with the rest of the linked list.
 * ----------------------------------
 * Time: O(n) | Space: O(1)
 */

// 2074. Reverse Nodes in Even Length Groups

// Time: O(n) | Space: O(1) 
var reverseEvenLengthGroups = function(head) {
    if (!head.next) {
        return head;
    }
    // Group after 1st node is size of 2: [i] 1,2.
    let groupSize = 2;
    let start = head;
    let prev = head;
    let curr = head.next;
    let count = 0;
    while (curr) {
        // revert only when when nodes count is equal to the group size.
        if (count === groupSize) {
            // to revert only even nodes-length group.
            if (count % 2 === 0) {
                // It will be the start of our next group.
                const end = curr;
                // After reverse this node will be the tail of the reverted list.
                const tail = start.next;
                // reverse everything in the middle of start and end 
                reverseList(start, end, count);
                start = tail;
            // when groupSize is even we don't need to reverse, 
            // but need to set the new start to the prev (group end) node.
            } else {
                start = prev;
            }
            // reset count and increment the group size.
            count = 0;
            groupSize++;
        // before count hit the groupSize
        } else {
            prev = curr;
            curr = curr.next;
            count++;
        }
    }
    // in the case where we ended early on even count
    if (count % 2 === 0) {
        reverseList(start, null, count);
    } 
    return head;
};

function reverseList(start, end, count) {
    // for case when we have a single node
    if (!start.next) {
        return start;
    }
    let prev = start;
    let curr = start.next;
    // At the end start.next will be the last node of the reverted list.
    let tail = start.next;
    
    for (let i = 0; i < count; i++) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    // prev is the first node of the reverted list.
    start.next = prev;
    // end is the continuation of our origin list.
    tail.next = end;
}

/*
 * In-place Reversal of a Linked List
 * ----------------------------------
 * Time: O(n) | Space: O(1)
 */

// 61. Rotate List

// Time: O(n) | Space: O(1)
var rotateRight = function(head, k) {
    let tmp = head;
    let end = null;
    let idx = 0;
    let length = 0;
    
    while (tmp) {
        if (!tmp.next) {
            end = tmp;
        }
        tmp = tmp.next;
        length++;
    }
    tmp = head;
    k = k % length;
    while (tmp) {
        if (idx === length - k - 1) {
            end.next = head;
            head = tmp.next;
            tmp.next = null;
            break;
        }
        tmp = tmp.next;
        idx++;
    }
    return head;
};

/*
Two Pointers
------------------------
1. Get list length.
2. Get end element.
3. Get element that will become new end.
4. Change poiners:

* current = [length - (k % length) - 1] element (new end)
* end.next = head
* head = current.next (new start)
* current.next = null
------------------------
Time: O(n) | Space: O(1)
*/

// 24. Swap Nodes in Pairs

// Time: O(n) | Space: O(1)
var swapPairs = function(head) {
    // No need to swap if less then two nodes.
    if (!head?.next) {
        return head;
    }
    let tmp = head;
    // Second node will be the new head after first swap.
    let resultHead = head.next;
    while (tmp?.next) {
        let curr = tmp;
        let swap = tmp.next;
        // The start of the remaining list.
        let next = tmp.next?.next;

        swap.next = curr;
        // Next node after swap is the result of the next swap 
        // or the next node if it is the last one
        // or undefined if current was the last one.
        curr.next = next?.next || next;

        tmp = next;
    }
    return resultHead;
};

/*
 * In-place Reversal of a Linked List
 * ----------------------------------
 * Time: O(n) | Space: O(1) 
 */