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
- Update the values around the nodes first
- Update the next pointers of each of the nodes to be swapped (a.next = b.next, b.next=temp.next — (temp = a))
- 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:
- Update the values around the nodes first
- Update the next pointers of each of the nodes to be swapped (a.next = b.next, b.next=temp — (temp = a))
- 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
}```
SOCIAL SHARE CARD GENERATOR