AndyPromiseU 2021-09-23 20:24 采纳率: 100%
浏览 62
已结题

Python实现反转链表,递归实现的问题

对长度为5的链表进行反转,递归实现,到表尾的时候,返回值p.val为5,但是在递归返回后p.val为4,还有递归返回后不在newhead=recurse(p.next),不原路返回,这是为什么?

img

class ListNode:
    def __init__(self,x):
        self.val=x
        self.next=None
 
def recurse(p):    #递归,head为原链表的头结点,newhead为反转后链表的头结点
    i = 0
    if p is None:
        return 
    if p.next is None:
        print("aaaa{}".format(p.val))
        return p
    else:

        newhead=recurse(p.next)
        p.next.next=p
        p.next=None
        i += 1
        
    return newhead
    
head=ListNode(1)               #测试代码
p1=ListNode(2)                 # 建立链表1->2->3->4->None
p2=ListNode(3)
p3=ListNode(4)
p4=ListNode(5)
head.next=p1
p1.next=p2
p2.next=p3
p3.next=p4

p=recurse(head)           #输出链表4->3->2->1->None
while p:
    print (p.val)
    p=p.next

  • 写回答

3条回答 默认 最新

  • 关注

    因为最后一个节点的next是None,直接返回return p。不再继续调用recurse(p.next)。
    之后递归开始回溯,执行 newhead=recurse(p.next) 之后的代码
    4到1要在递归回溯时输出

    class ListNode:
        def __init__(self,x):
            self.val=x
            self.next=None
    def recurse(p):    #递归,head为原链表的头结点,newhead为反转后链表的头结点
        i = 0
        if p is None:
            return
        if p.next is None:
            print("aaaa{}".format(p.val)) #输出5
            return p
        else:
            newhead=recurse(p.next)
            print("bbbb{}".format(p.val)) #递归回溯时输出4到1
            p.next.next=p
            p.next=None
            i += 1
        return newhead
    
    
    head=ListNode(1)               #测试代码
    p1=ListNode(2)                 # 建立链表1->2->3->4->None
    p2=ListNode(3)
    p3=ListNode(4)
    p4=ListNode(5)
    head.next=p1
    p1.next=p2
    p2.next=p3
    p3.next=p4
    p=recurse(head)           #输出链表4->3->2->1->None
    while p:
        print (p.val)
        p=p.next
    

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 10月1日
  • 已采纳回答 9月23日
  • 修改了问题 9月23日
  • 创建了问题 9月23日

悬赏问题

  • ¥150 寻找王者荣耀开发作者,合作或者解答
  • ¥15 乳腺癌数据集 相关矩阵 特征选择
  • ¥15 我的游戏账号被盗取,请问我该怎么做
  • ¥15 通关usb3.0.push文件,导致usb频繁断连
  • ¥15 有没有能解决微信公众号,只能实时拍照,没有选择相册上传功能,我不懂任何技术,,有没有给我发个软件就能搞定的方法
  • ¥15 Pythontxt文本可视化
  • ¥15 如何基于Ryu环境下使用scapy包进行数据包构造
  • ¥15 springboot国际化
  • ¥15 搭建QEMU环境运行OP-TEE出现错误
  • ¥15 Minifilter文件保护