Leetcode Pattern 4 Linked List

# prev -> next
# Insert cur
cur.next = prev.next
prev.next = cur

# If we do not use dummy head, we have to deal with edge case: Adding in front of head
cur.next = head
head = cur

# prev -> cur -> next
prev.next = cur.next

# If we do not use dummy head, we have to deal with edge case: Deleting the head
head = head.next

// Recursive method
function reverseList(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) return head;

    const nextHead = reverseList(head.next);
    // the last node of nextHead linked list is head.next.
    // We will put head as the last node of the nextHead linked list
    head.next.next = head;
    head.next = null;
    return nextHead;
};

// Iterative method
function reverseList(head: ListNode | null): ListNode | null {
    let newHead: ListNode | null = null
    let current = head;
    while (current) {
        // back up current.next
        const nextNode = current.next;

        // Insert the current in front of newHead and update newHead with current
        current.next = newHead;
        newHead = current;

        // update current with current.next
        current = nextNode;
    }
    return newHead;
};

const findNthNode = (head: ListNode | null, nth: number): ListNode | null => {
    let p = head;
    let count = 1;
    while (p !== null) {
        if (count === nth) {
            return p;
        }
        count += 1;
        p = p.next;
    }
    return null;
}

function reverseList(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) return head;

    const nextHead = reverseList(head.next);
    // the last node of nextHead linked list is head.next.
    // We will put head as the last node of the nextHead linked list
    head.next.next = head;
    head.next = null;
    return nextHead;
};

function reverseList(head: ListNode | null): ListNode | null {
    let newHead: ListNode | null = null
    let current = head;
    while (current) {
        // back up current.next
        const nextNode = current.next;

        // Insert the current in front of newHead and update newHead with current
        current.next = newHead;
        newHead = current;

        // update current with current.next
        current = nextNode;
    }
    return newHead;
};

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    const reverseList = (head: ListNode | null): ListNode | null => {
        if (head === null || head.next === null) return head;
        const ans = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return ans;
    };
    const findNthNode = (head: ListNode | null, nth: number): ListNode | null => {
        let p = head;
        let count = 1;
        while (p !== null) {
            if (count === nth) {
                return p;
            }
            count += 1;
            p = p.next;
        }
        return null;
    }
    const calSize = (head: ListNode | null): number => {
        let count = 0;
        let p = head;
        while (p !== null) {
            p = p.next
            count += 1;
        }
        return count;
    };
    const size = calSize(head);
    if (left === right) return head;

    if (left === 1) {
        if (size === right) {
            return reverseList(head);
        } else {
            const p = findNthNode(head, right);
            const pNext = p.next;
            p.next = null;
            const newHead = reverseList(head);
            // Now head is the last node and we put pNext behind it.
            head.next = pNext;
            return newHead;
        }
    }
    // Find left and right node and the one before left and the one after right.
    const preLeftNode = findNthNode(head, left - 1);
    const leftNode = preLeftNode.next;
    const rightNode = findNthNode(head, right);
    const afterRightNode = rightNode.next;
    // Make the middle part a single linked list.
    preLeftNode.next = null;
    rightNode.next = null;
    // reverse the middle part
    reverseList(leftNode);
    // Join it back
    preLeftNode.next = rightNode;
    leftNode.next = afterRightNode;
    return head;
};

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    const reverseList = (head: ListNode | null): ListNode | null => {
        if (head === null || head.next === null) return head;
        const ans = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return ans;
    };
    const findNthNode = (head: ListNode | null, nth: number): ListNode | null => {
        let p = head;
        let count = 1;
        while (p !== null) {
            if (count === nth) {
                return p;
            }
            count += 1;
            p = p.next;
        }
        return null;
    }
    const dummy = new ListNode(0);
    dummy.next = head;
    let preLeft = dummy;
    let left = head;
    let right = head;
    while (true) {
        right = findNthNode(left, k);
        if (right === null) break;
        // backup right.next
        const rightNext = right.next;
        // Make the block a single linked list.
        preLeft.next = null;
        right.next = null;
        // Reverse it
        reverseList(left);
        // Join it back
        preLeft.next = right;
        left.next = rightNext;
        // Move preLeft and left forward.
        preLeft = left;
        left = preLeft.next;
    }
    return dummy.next;
};

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (head === null) return head;
    const calSize = (head: ListNode | null): number => {
        let count = 0;
        let p = head;
        while (p !== null) {
            p = p.next
            count += 1;
        }
        return count;
    };
    const n = calSize(head);

    k = k % n;
    if (k === 0) return head;

    const findNthNode = (head: ListNode | null, nth: number): ListNode | null => {
        let p = head;
        let count = 1;
        while (p !== null) {
            if (count === nth) {
                return p;
            }
            count += 1;
            p = p.next;
        }
        return null;
    };
    const newEnd = findNthNode(head, n - k);
    const newHead = newEnd.next;
    newEnd.next = null;
    // cut it in the middle.
    // Find the lastNode
    let p = newHead;
    while (p.next !== null) {
        p = p.next;
    }
    p.next = head;
    return newHead;
};

function deleteDuplicates(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) return head;
    let p = head;
    let pNext = head.next;
    while (pNext !== null) {
        if (p.val === pNext.val) {
            // Remove pNext
            p.next = pNext.next;
        } else {
            p = p.next;
        }
        pNext = p.next;
    }
    return head;
};

function deleteDuplicates(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) return head;
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    let cur = head;
    let next = head.next;
    while (next !== null) {
        if (cur.val === next.val) {
            // Find the end of the same values
            while (next !== null && cur.val === next.val) {
                next = next.next;
            }
            // next.val is not cur.val
            // Drop all nodes between prev and next.
            prev.next = next;

            cur = next;
            if (next === null) continue; // reach the end.
            next = next.next;
        } else {
            prev = cur;
            cur = next;
            next = next.next;
        }
    }
    return dummy.next;
};

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0);
    let p = dummy;
    let p1 = list1;
    let p2 = list2;
    while (p1 !== null && p2 !== null) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if (p1 !== null) {
        p.next = p1;
    }
    if (p2 !== null) {
        p.next = p2;
    }
    return dummy.next;
};

function partition(head: ListNode | null, x: number): ListNode | null {
    const dummy1 = new ListNode(0);
    const dummy2 = new ListNode(0);
    let p1 = dummy1;
    let p2 = dummy2;
    let p = head;
    while (p !== null) {
        if (p.val < x) {
            p1.next = p;
            p1 = p1.next;
            p = p.next;
            p1.next = null;
        } else {
            p2.next = p;
            p2 = p2.next;
            p = p.next;
            p2.next = null;
        }
    }
    // Find the last Node of linked List 1.
    p = dummy1;
    while (p.next !== null) {
        p = p.next;
    }
    // Link the linked list 2 to the Linked list 1
    p.next = dummy2.next;
    return dummy1.next;
};

// Find the middle point with fast and slow pointer and user merge sort to merge them.
function sortList(head: ListNode | null): ListNode | null {
    if (head === null) return null;
    if (head.next === null) return head;
    const findMiddleNode = (head: ListNode): ListNode => {
        let fast = head.next;// It is not head.
        let slow = head;
        while (fast !== null && fast.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        const mid = slow.next; //This is the middle point.
        slow.next = null; // set the first half end null.
        return mid;
    };
    const mid = findMiddleNode(head);

    const mergeList = (head1: ListNode| null, head2: ListNode| null): ListNode | null => {
        const dummy = new ListNode(0);
        let p = dummy;
        let p1 = head1;
        let p2 = head2;
        while (p1 !== null && p2 !== null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p.next.next = null;
            p = p.next;
        }
        if (p1 !== null) {
            p.next = p1;
        }
        if (p2 !== null) {
            p.next = p2;
        }
        return dummy.next;
    };
    return mergeList(sortList(head), sortList(mid));
};

function copyRandomList(head: _Node | null): _Node | null {
    // Copy the linear structure.
    const dummy = new _Node(0);
    let p1 = head;
    let p2 = dummy;
    while (p1 !== null) {
        p2.next = new _Node(p1.val);
        p2 = p2.next;
        p1 = p1.next;
    }

    // Copy the random pointer
    p1 = head;
    p2 = dummy.next;
    while (p1 !== null && p2 !== null) {
        const random1 = p1.random;
        if (random1 !== null) {
            let q1 = head;
            let q2 = dummy.next;
            while (q1 !== null && q2 !== null) {
                if (q1 === random1) {
                    p2.random = q2; // Update the random pointer
                    break;
                }
                q1 = q1.next;
                q2 = q2.next;
            }
            // p2.random = random2;
        }
        p2 = p2.next;
        p1 = p1.next;
    }
    return dummy.next;
};

class Node {
    public val: number;
    public next: Node;
    constructor(val: number) {
        this.val = val;
        this.next = null;
    }
}

class MyLinkedList {
    private head: Node | null;
    private size: number;

    constructor() {
        this.head = null;
        this.size = 0;
    }

    getNode(index: number): Node | null {
        if (index >= this.size) return null;
        let p = this.head;
        let count = 0;
        while (p !== null) {
            if (count === index) {
                return p;
            }
            count += 1;
            p = p.next;
        }
        return null;
    }

    get(index: number): number {
        const node = this.getNode(index);
        if (node === null) return -1;
        return node.val;
    }

    addAtHead(val: number): void {
        this.addAtIndex(0, val);
    }

    addAtTail(val: number): void {
        this.addAtIndex(this.size, val);
    }

    addAtIndex(index: number, val: number): void {
        if (index > this.size) {
            return;
        }
        if (index === 0) {
            const newHead = new Node(val);
            newHead.next = this.head;
            this.head = newHead;
        } else {
            const preNode = this.getNode(index - 1);
            const preNodeNext = preNode.next;
            preNode.next = new Node(val);
            preNode.next.next = preNodeNext;
        }
        this.size += 1;
    }

    deleteAtIndex(index: number): void {
        if (index >= this.size) {
            return;
        }
        if (index === 0) {
            this.head = this.head.next;
        } else {
            const preNode = this.getNode(index - 1);
            preNode.next = preNode.next.next;
        }
        this.size -= 1;
    }
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    const getCount = (head: ListNode | null): number => {
        let count = 0;
        let p = head;
        while (p !== null) {
            p = p.next;
            count += 1;
        }
        return count;
    };
    let countA = getCount(headA);
    let countB = getCount(headB);
    // make sure headA is shorter or equal to headB.
    if (countA > countB) {
        [countA, countB] = [countB, countA];
        [headA, headB]   = [headB, headA];
    }
    if (countA < countB) {
        // remove nodes in B to make they are equal.
        while (countA < countB) {
            headB = headB.next;
            countB -= 1;
        }
    }
    // now countA = countB
    while (headA !== headB) {
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
};

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let front = head;
    for (let i = 0; i < n; i++) {
        front = front.next;
    }
    // the head is the one to be deleted.
    if (front === null) {
        return head.next;
    }
    let back = head;
    while (front.next !== null) {
        front = front.next;
        back = back.next;
    }
    back.next = back.next.next;
    return head;
};

function removeElements(head: ListNode | null, val: number): ListNode | null {
    if (head === null) return head;
    // Remove the head
    if (head.val === val) return removeElements(head.next, val);
    // move to the next node.
    head.next = removeElements(head.next, val);
    return head;
};

function oddEvenList(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null || head.next.next === null) return head;

    const oddDummy = new ListNode(0);
    const evenDummy = new ListNode(0);
    let count = 1;
    let p = head;
    let oddP = oddDummy;
    let evenP = evenDummy;
    while (p !== null) {
        if (count % 2 === 1) { // oddDummy
            // Put it behind the odd linked list
            oddP.next = p;
            p = p.next;
            oddP = oddP.next;
            oddP.next = null;
        } else { // evenDummy
            // Put it behind the even linked list
            evenP.next = p;
            p = p.next;
            evenP = evenP.next;
            evenP.next = null;
        }
        count += 1;
    }
    oddP.next = evenDummy.next;
    return oddDummy.next;
};

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0);
    let p = dummy;
    let p1 = l1;
    let p2 = l2;
    let carry = 0;
    while (p1 !== null || p2 !== null) {
        const val1 = p1 === null ? 0 : p1.val;
        const val2 = p2 === null ? 0 : p2.val;
        let sum = val1 + val2 + carry;
        carry = sum > 9 ? 1 : 0;
        sum = sum > 9 ? sum - 10 : sum;
        p.next = new ListNode(sum);
        p = p.next;
        if (p1 !== null) {
            p1 = p1.next;
        }
        if (p2 !== null) {
            p2 = p2.next;
        }
    }
    if (carry > 0) {
        p.next = new ListNode(carry);
    }
    return dummy.next;
};

function flatten(head: _Node | null): _Node | null {
    // return head and tail node after it is flattened.
    const solver = (head: _Node | null): [_Node | null, _Node | null] => {
        if (head === null) return [null, null];
        let p = head;
        while (p.next !== null && p.child === null) {
            p = p.next;
        }
        // p.next === null || p.child !== null
        // Reach the tail node
        if (p.next === null) {
            // p is the tail node.
            if (p.child === null) {
                // If it has no child, simply return head and tail.
                return [head, p];
            }
            const [newHead, newTail] = solver(p.child);
            p.child = null;
            newHead.prev = p;
            p.next = newHead;
            return [head, newTail];
        }
        // Find a middle node with child.
        const [newHead, newTail] = solver(p.child);
        p.child = null;
        const pNext = p.next;
        p.next = newHead;
        newHead.prev = p;


        const [newRestHead, newRestTail] = solver(pNext);
        newTail.next = newRestHead;
        newRestHead.prev = newTail;
        return [head, newRestTail]
    }
    const [newHead, newTail] = solver(head);
    return newHead;
};

function insert(head: _Node | null, insertVal: number): _Node | null {
    const node = new _Node(insertVal);
    // Zero node, we can simply insert it.
    if (head === null) {
        node.next = node;
        return node;
    };
    let p = head;
    while (p.next !== head) {
        // p.next.val > p.val and insertVal is within this range.
        if (insertVal >= p.val && insertVal < p.next.val) {
            break;
        }
        // p.next.val < p.val and insertVal is outside of this range.
        // Insert it to falling cliff.
        if (p.val > p.next.val && (insertVal >= p.val || insertVal <= p.next.val)) {
            break;
        }
        p = p.next;
    }
    // Otherwise, insert to the head.
    const next = p.next;
    p.next = node;
    node.next = next;
    return head;
}