使用递归的反向链表问题

Question

我正在尝试使用递归来反转链表。一切顺利，直到最后，我最终得到了失败的结果。

谁能告诉我哪里做错了？

const reverseLinkedList = (node, newChildOldParent=null ) => {
    if( node.next ){
        reverseLinkedList(node.next, node);
    }
    node.next = newChildOldParent;
    return node;
}

const someList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: null
            }
        }
    }
};

console.log(reverseLinkedList( someList ))

我明白了

{ value: 1, next: null }

而不是反向链表。

我哪里错了？

Answer 1

反转工作正常，但您失去了对新磁头的追踪，而是 return 现在指向 null 的旧磁头。这是堆栈调用的图表：

curr: 1 next: 2
  curr: 2 next: 3
    curr 3: next: 4
      curr: 4 next: null
      curr: 4 next: 3
    curr: 3 next: 2
  curr: 2 next: 1
curr: 1 next: null <-- uh oh

您需要跟踪新的头部，即节点 4。这是将最后一个节点传递回头部的另一种方法：

const reverseLinkedList = (curr, prev) => {
    if (curr.next) {
        const newHead = reverseLinkedList(curr.next, curr);
        curr.next = prev;
        return newHead; // pass the new head up the list
    }
    
    curr.next = prev;
    return curr; // base case; return the tail
};

const someList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: null
            }
        }
    }
};

console.log(reverseLinkedList(someList));

使用递归的反向链表问题

Issues with reverse Linked List using recursion

javascript

algorithm

recursion

linked-list

singly-linked-list