Rotate Doubly Linked List By k
Fri Apr 19 2024 Finding the Cut-Off Point:
Identifying the node at size - k position to determine where the list should be cut and rearranged.
Reconnecting Nodes:
After severing the list at the cut-off, the tail of the list is connected to the original head, and the node at the cut-off becomes the new head of the list.
Adjusting Previous Pointers:
Since it's a doubly linked list, ensuring that prev pointers are correctly reassigned is crucial to allow bidirectional traversal without errors.
1class Node {
2 constructor(val) {
3 this.val = val;
4 this.next = null;
5 this.prev = null;
6 }
7}
8
9class DoublyLinkedList{
10 constructor(val) {
11 this.head = null;
12 this.tail = null;
13 }
14 addLast(val) {
15 const newNode = new Node(val);
16 if(!this.head) {
17 this.head = newNode;
18 this.tail = newNode;
19 return
20 }
21 newNode.prev = this.tail;
22 this.tail.next = newNode;
23 this.tail = newNode;
24 }
25 size() {
26 let current = this.head;
27 let length = 0;
28 while (current) {
29 length++;
30 current = current.next;
31 }
32 return length;
33 }
34 print() {
35 let outputString = '';
36 let current = this.head;
37 while (current) {
38 outputString += current.val + '<->';
39 current = current.next;
40 }
41 console.log(outputString + 'null');
42 }
43 rotateByK(k){
44 let current = this.head;
45 let prev = null;
46 let cutOffPoint = this.size() - k;
47 let movement = 0;
48 while (movement < cutOffPoint) {
49 movement++;
50 prev = current;
51 current = current.next;
52 }
53
54 let newHead = current;
55
56 let newCurrent = current;
57 prev.next = null;
58
59 while (newCurrent.next) {
60 newCurrent = newCurrent.next;
61 }
62
63 newCurrent.next = this.head;
64
65 this.head = newHead;
66
67 }
68
69}
70let dll = new DoublyLinkedList();
71dll.addLast(1);
72dll.addLast(2);
73dll.addLast(3);
74dll.addLast(4);
75dll.addLast(5);
76console.log(dll.size())
77dll.rotateByK(2);
78dll.print();