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

发布时间：2020-12-20 09:54:42 所属栏目：Python 来源：网络整理

导读：问题描述：反转一个单链表。示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？首先是迭代方式： # Definition for singly-linked list. # class ListNode: def __init__(self,x): self.v

问题描述：

反转一个单链表。

示例:

输入: 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
         p1

过程：

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

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

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

结果：

递归版本的：

head.next
        p2=self.reverseList(p1)
        head.next=None
        p1.next= p2

过程：

首先是：

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

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

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

依次递推即可：

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

p2=self.reverseList(p1)

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

head.next=None

p1.next=head

最后返回p2即可。

结果：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!