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

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条)

相关推荐 更多相似问题