投稿
  1. 我是皮皮虾首页
  2. 编程开发

Leecode – 反转单链表

站长 • • 编程开发

原题

输入[1,2,3,4,5]

输出[5,4,3,2,1]

  1. https://leetcode-cn.com/problems/reverse-linked-list/

解答

思路：

1->2->3->-4>-5->null

先定义个前驱指针，指向null，prev = None

再定义一个当前指针，指向当前函数传入的值，也就是head，curr = head

循环遍历链表，遍历链表都是从当前节点开始的，这里的遍历只能用while，不能用for，因为你不知道长度

循环体内：

先用tmp 记录当前节点的下一个节点，tmp = curr.next

再把当前节点的下一个节点指向前驱节点，curr.next = prev

前驱节点指向当前节点，prev = curr,其实这2步目的是将前驱节点后移

再将当前节点后往后移动一个，也就是指向了下一个节点，目的是，下一次遍历从这个节点开始，curr = tmp

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
        return prev

记忆方式

我的记忆方式很简单，只记忆循环体的内容，其他的硬记了。

循环体分为4步，先记第一步和第四部。也就是用tmp 记录下当前节点的下一个节点，再将当前节点指向下一个节点

tmp = curr.next
xxx
xxx
curr = tmp

再记中间2步，中间的步骤目的是将前驱节点指向当前节点，也就是先将当前节点的下一个节点指向前驱节点，再把前驱节点指向当前节点。互相指向对方

curr.next = pre
pre = curr

原创文章，作者：站长，如若转载，请注明出处：https://wsppx.cn/865/%e7%bd%91%e7%bb%9c%e5%bc%80%e5%8f%91/

赞 (0)
打赏 微信扫一扫 微信扫一扫
站长站长
0 1
« 上一篇 2021年8月2日 am9:16
下一篇 » 2021年8月2日 am11:27

相关推荐

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

记住昵称、邮箱和网址，下次评论免输入

评论列表（1条）

  • 站长
    站长 2021年8月17日 上午10:40

    去面试迅雷就问了这个题目，真实日狗了，2周就忘记了。。

    回复