Reputation: 371
Input: 5 -> 9 -> 8 -> 3 -> 1 -> 7
Expected Output: 7 -> 1 -> 3 -> 8 -> 9 -> 5
Issue:
When I display the reversed linked list the result is 5. This is an issue because this should be the tail and not the head. The rest of the nodes are missing in the display well.
Question:
Is there an issue with the code base that is preventing the traversal from the head to the tail and changing the pointers to reverse the list?
Code:
LinkedList:
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
insertFirst(item) {
if (this.head !== null) {
const newHead = new _Node(item);
let oldHead = this.head;
oldHead.prev = newHead;
newHead.next = oldHead;
this.head = newHead;
} else {
this.head = new _Node(item, this.head);
}
this.size++;
}
insertLast(item) {
if (!this.head) {
this.insertFirst(item);
} else {
let tempNode = this.head;
while (tempNode.next !== null) {
tempNode = tempNode.next;
}
tempNode.next = new _Node(item, null, tempNode);
}
this.size++
}
}
module.exports = LinkedList;
Main:
const LinkedList = require("./LinkedLists");
const { reverse } = require("./Reverse");
const { display } = require("./Supplemental");
function main() {
let SLL = new LinkedList();
SLL.insertFirst(5);
SLL.insertLast(9);
SLL.insertLast(8);
SLL.insertLast(3);
SLL.insertLast(1);
SLL.insertLast(7);
reverse(SLL);
display(SLL);
return SLL;
}
console.log(main());
Reverse:
reverse = (SLL) => {
let curr = SLL.head
if (!curr) {
return;
}
if (!curr.next) {
SLL.head = curr;
return;
}
let tmp = reverse(curr.next);
curr.next.next = curr;
curr.next = null;
return tmp;
}
module.exports = { reverse };
Display:
display = (SLL) => {
let currentNode = SLL.head;
if (!SLL.head) {
return null;
}
while (currentNode !== null) {
console.log(currentNode.value);
currentNode = currentNode.next;
}
return;
};
Upvotes: 0
Views: 107
Reputation: 371
Can someone tell me what return tmp
is doing in the Reverse.js file?
(1) Removed display from Main.js
(2) Edited Main.js:
const LinkedList = require("./LinkedLists");
const { reverse } = require("./Reverse");
const { display } = require("./Supplemental");
function main() {
let SLL = new LinkedList();
SLL.insertFirst(5);
SLL.insertLast(9);
SLL.insertLast(8);
SLL.insertLast(3);
SLL.insertLast(1);
SLL.insertLast(7);
const result = reverse(SLL.head);
console.log(result);
return SLL;
}
return main();
(3) Edited Reverse.js:
reverse = (curr, prev = null) => {
if (!curr) {
return prev;
}
let tmp = reverse(curr.next, curr);
const temp = curr.next;
curr.next = prev;
curr.prev = temp;
return tmp;
}
module.exports = { reverse };
Upvotes: 0