Reverse k Segments in Linked List

A few things come to mind after spending almost 24 hours working on this problem. When swapping elements in a linked list always follow these steps:

Swapping distant from each other

1. Update the values around the nodes first
2. Update the next pointers of each of the nodes to be swapped (a.next = b.next, b.next=temp.next — (temp = a))
3. Update the prev pointers of each of the nodes to be swapped (a.prev=b.prev, b.prev=temp.prev — (temp=a))

This is crucial because doing this the wrong way will result in something called circular references where instead of the linked list be linear, it contains a node that ‘circles’ back to another node found earlier in the list.

Swapping nodes when both are next to each other

Instead of swapping nodes that are distant from each other, you can run into scenarios where the nodes are right next to each other. In this case:

1. Update the values around the nodes first
2. Update the next pointers of each of the nodes to be swapped (a.next = b.next, b.next=temp — (temp = a))
3. Update the prev pointers of each of the nodes to be swapped (a.prev=b, b.prev=temp.prev — (temp=a))

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let length = 1
    let node = head

    if(k <= 1) return head

    // get length and tail
    while(node.next) {
        node = node.next
        length++
    }
    let tail = node

    // doubly link
    // get tail
    let doublyNode = head
    while(doublyNode.next) {
        let prev = doublyNode
        doublyNode = doublyNode.next
        doublyNode.prev = prev
    }
    let segmentsAmt = Math.floor(length / k)
    let currSegment = 0

    const updateEnds = (a, b) => {
        if(a === head) head = b
        if(b === tail) tail = a
    }

    const reverse = (startSegment, k) => {
        const sideSwap = (a, b) => {
            if(a.prev) a.prev.next = b
            if(b.next) b.next.prev = a

            a.next = b.next
            b.next = a

            const temp = getTempNode(a)
            a.prev = b
            b.prev = temp.prev

            updateEnds(a, b)
        }

        const swap = (a, b) => {
            if(a.prev) a.prev.next = b
            if(a.next) a.next.prev = b
            if(b.next) b.next.prev = a
            if(b.prev) b.prev.next = a

            const temp = getTempNode(a)
            a.next = b.next
            b.next = temp.next

            a.prev = b.prev
            b.prev = temp.prev

            updateEnds(a, b)
        }

        let needle = 0;
        const kIdx = k - 1
        while(needle < Math.floor(k/2)) {
            const aIdx = (startSegment * k) + needle
            const bIdx = (startSegment * k) + (kIdx - needle) 
            const a = nodeAtIdx(head, aIdx)
            const b = nodeAtIdx(head, bIdx)
            if(bIdx - aIdx === 1) {
                sideSwap(a,b)
            } else {
                swap(a, b)
            }
            needle++
        }
    }

    while(currSegment < segmentsAmt) {
        reverse(currSegment, k)
        currSegment++
    }

    return head
};

const nodeAtIdx = (head, idx) => {
    let node = head
    let i = 0;
    while(i < idx) {
        node = node.next
        i++
    }
    return node
}

const getTempNode = (node) => {
    const temp = new ListNode(node.val, node.next)
    temp.prev = node.prev
    return temp
}```