Reversing a linked list - Error says found cycle-CodePudding

I wrote the following code to reverse a linked list, but not sure what I am doing incorrectly. This is from a sample problem here that asks to reverse a linked list.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    function traverse(node) {
        if(!node.next) return node;
        else {
            let currentNode = node.next;
            let nextNode = traverse(node.next);
            nextNode.next = currentNode;
            return nextNode;
        }
    }
    
    return traverse(head);
};

For the given input , [4,5], when I try to run it says Error - Found cycle in the ListNode. Could someone please explain what am I doing wrong here?

CodePudding user response：

The problem here is that you're always returning last node of linked list in traverse(node.next) which then changes it's next causing a loop to get formed.
Consider a linked list, 1 -> 2 -> 3 -> 4.
Recursive calls are:
traverse(1) -> traverse(2) -> traverse(3) -> traverse(4)

traverse(4) - returns 4.
traverse(3) - 4.next=3 and returns 4.
traverse(2) - 4.next=2 and returns 4.
traverse(1) - 4.next=1 and returns 4.

Hence, a cyclic linked list is formed: 1->2->3->4->1...

Instead you should change the next in place during traverse call, similar to this:

var reverseList = function(head) {
    function traverse(node) {
        if(!node || !node.next) return node;
        else {
            let currentNode = node;
            let nextNode = node.next;
            let head = traverse(node.next);
            nextNode.next = currentNode;
            currentNode.next = null;
            return head;
        }
    }
    
    return traverse(head);
};

CodePudding user response：

The problem is that you did not clear head.next, it still points to the second (now next-to-last) node. You could fix this by doing

const last = traverse(head);
last.next = null;
return last;

but this code is still buggy as it can only handle non-empty lists, and really it probably should not mutate the argument list at all but rather produce a new one. That immutable style is also much, much simpler:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
    function traverse(node, tail) {
        if (!node) return tail;
        else return traverse(node.next, new ListNode(node.val, tail));
    }
    return traverse(head, null);
}

CodePudding user response：

I don't see why we need recursion here. We just need to keep track of the next node to alter and the head of the new list. Like:

var reverseList = function(head) {
  let newHead = null;

  while (head) {
    const node = head;
    head = node.next;
    node.next = newHead;
    newHead = node;
  }

  return newHead;
};