递归反转链表出错求助：输入[1,2,3,4,5,6,-1]仅得[1->None]

你的递归反转链表逻辑本身是正确的，问题出在调用反转函数后没有接收返回的新链表头。

错误原因 #

reverseLL函数返回的是反转后的链表新头部，但你调用时只执行了reverseLL(head)，没有把这个新头赋值给head变量。此时原来的head指向的是原链表的第一个节点（也就是反转后的链表最后一个节点），它的next已经被设置为None，所以打印时只会输出1->None。

修正后的代码 #

只需要修改调用反转函数的行，将返回值赋值给head：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def takeInput():
    inputList = [int(ele) for ele in input().split()]
    head = None
    for i in inputList:
        if i == -1:
            break
        newNode = Node(i)
        if head is None:
            head = newNode
            tail = newNode
        else:
            tail.next = newNode
            tail = newNode
    return head

def printLL(head):
    while head is not None:
        print(str(head.data) + "->", end="")
        head = head.next 
    print("None")
    return

def reverseLL(head):
    if head is None or head.next is None:
        return head
    rest = reverseLL(head.next)
    head.next.next = head
    head.next = None
    return rest
   

head = takeInput()
printLL(head)
# 接收反转后的新头
head = reverseLL(head)
printLL(head)

验证结果 #

输入1 2 3 4 5 6 -1后，输出会变成：

1->2->3->4->5->6->None
6->5->4->3->2->1->None

内容的提问来源于stack exchange，提问作者Ratnesh