Reverse Doubly Linked List - Is my code correct?

JavaScript
1

Tell us what’s happening:
I was struggling for a long time with this one. I understand the idea conceptually of a doubly linked list, but implementing a reverse function has been difficult. I at first thought that simply switching the head and tail node would do the trick, but I was not successful in doing that as I was having issues with references and I added an add function that apparently was conflicting with the tests…

After some time and through many iterations, I went back to my hypothesis of switching the head and tail node data and then my code passed… really confused here. I’m not sure if I “tricked” the test suite or if my code is actually correct. I think I may have passed by accident. Does anyone know if my code below is actually correct?

Your code so far


var Node = function(data, prev) {
this.data = data;
this.prev = prev;
this.next = null;
};
var DoublyLinkedList = function() {
this.head = null;
this.tail = null;
// Only change code below this line
this.reverse = function() {
  if (this.head === null || this.tail === null) return null;

  let head = this.head.data;
  let tail = this.tail.data;

  this.tail.data = head;
  this.head.data = tail;

}
// Only change code above this line
};

// var d = new DoublyLinkedList();
// d.add('A: HEAD');
// d.add('B');
// d.add('C');
// d.add('D: TAIL');
// d.reverse();
// console.log(d);

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/86.0.4240.198 Safari/537.36.

Challenge: Reverse a Doubly Linked List

Link to the challenge:

2

Hey @jawaka72, I don’t know what is happening under the hood but if your reverse function is called for each node by iterating through the whole linked-list, then it seems you passed the test correctly. To reverse Linkedlist you need to swap the head and the tail of each node in the list, and that is what your function is doing right?.

3

Hey @abdirahman.omar.hash, my reverse function isn’t iterating. All I’m doing is swapping the head and tail data with each other. Iteration through the list makes a lot of sense which is why I feel like my solution is an anomaly because I solve the test cases without iteration.

4

@jawaka72 what I’m saying is what if the iteration is done under the hood and writing the swapping function is the task you supposed to accomplish? If you want to practice Linked lists you can implement outside FCC for your own, sometimes the hidden code in FCC challenges cause confusion.

1 Like
5

Ah, yes, I see what you mean now. There might be iteration done under the hood. I kinda doubt it because I feel like they want you to come up with the data structure on your own, but it is a possibility. I went ahead and tried again with iteration and looked at some YouTube videos to help explain what’s happening, so I’m starting to understand the implementation. Thanks for the suggestion.

6

There is actually a bug in the last two tests that allows your incorrect solution to pass. Try passing adding one additional value to the list and you will see your list is not in the correct order. The tests were only adding 3 values, so you just got lucky by swapping the head and tail.

I have submitted a pull request to fix this kind of solution from passing in the future.

2 Likes