Reverse k Segments in Linked List

[MyrinNew]

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
}```








More...