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

概述问题描述： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL进阶:你可

问题描述：

反转一个单链表。

示例:

输入: 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 = Noneclass 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即可。

结果：

总结

以上是内存溢出为你收集整理的【python-leetcode206-翻转链表】反转链表全部内容，希望文章能够帮你解决【python-leetcode206-翻转链表】反转链表所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。