首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【python-leetcode206-翻转链表】反转链表

【python-leetcode206-翻转链表】反转链表

作者头像
西西嘛呦
发布2020-08-26 09:50:05
6060
发布2020-08-26 09:50:05
举报

问题描述:

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

首先是迭代方式:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or head.next == None:
            return head
        p1=None
        p2=head
        while p2:
            t=p2.next
            p2.next = p1
            p1 = p2
            p2 = t
        return p1
        
        

过程:

关键之处,先要找到p2的下一个节点,然后再断开p2.next并指向p1

然后p1,p2同时右移,保证p1每次都在p2的前面

这样每次就可以让p2.next=p1

结果:

递归版本的:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or head.next == None:
            return head
        p1=head.next
        p2=self.reverseList(p1)
        head.next=None
        p1.next=head
        return p2

过程:

首先是:

然后是以p1为头结点的链表:

依次类推直到头结点不为空或头结点的下一节点不为空,也就是:

此时此时返回的值就是p2,也就是最后一个节点。之后就翻转当前的链表:

依次递推即可:

需要明确的是:先会一直执行:

p2=self.reverseList(p1)

得到返回值之后才会执行:

head.next=None

p1.next=head

最后返回p2即可。

结果:

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-02-25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档