java - 递归反向链表，最后一个节点是否应该指向null？

Question

我试图了解反向链接列表的递归方式。

    public ListNode reverseList2(ListNode head) {

        if(head == null || head.next == null) {
            return head;
        }

        ListNode newHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;

    }

反向链表

1->2->3->null

答案是

3->2->1->null

据我了解，最后一个节点应该指向空。但是在这个递归函数中，当它反转最后一个节点时，它并没有将它指向空。可以吗，最后一个节点不指向空？还是我错过了什么？

标签： javarecursionlinked-list

Answer 1

你是榜样。但是，当您删除该行时它不起作用head.next = null;

public ListNode reverseList2(ListNode head) {

    if(head == null || head.next == null) {
        return head;
    }

    ListNode newHead = reverseList2(head.next);
    head.next.next = head;

    return newHead;

}

它变成一个循环链表，其中尾部指向头部。你可能不小心忘记了那条线，然后尾巴没有指向空值。这是因为该行确保如果您在最后，下一个等于 null。