Leetcode 系列 | 反转链表

第一时间关注 AI 和 Python 知识

最近会更新一个 leetcode 的刷题系列,每次更新一道题目,并且通过画图辅助介绍自己的解题思路,大家如果有更好的解题思路也欢迎在文末留言,或者公众号后台回复,也可以添加我微信,进行交流,谢谢!

题目 | 206_Reverse_Linked_List

链接 | https://leetcode.com/problems/reverse-linked-list/

题目

给定一个链表,反转并输出结果。

示例

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

思路

反转一个单链表,首先肯定需要遍历这个单链表,在遍历的时候就希望修改当前结点的 next 指针,指向其前一个结点,因此肯定需要一个保存前一个结点的变量,也就是反转后链表的头部指针。

实现的思路应该是这样的:

  1. 首先定义一个 prev 保存前一个结点,curr 保存当前结点,然后还有一个 nxt 保存下一个结点,其中 prev 就是最终的反转链表的头结点;
  2. 先让 nxt 保存下一个结点;
  3. 然后改变 currnext 指针,指向前一个结点,即 prev ;
  4. 接着,让 prev = curr
  5. 最后,就是让 curr = nxt,指向下一个结点
  6. 重复 2-5 步,直到当前结点为空。

下图展示了上述几个步骤的过程:

实现

方法1

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        prev,curr = None,head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

方法2:更加简洁的版本

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        reversed_head = None
        current = head
        while current:
            reversed_head, reversed_head.next, current = current, reversed_head, current.next
        return reversed_head

github地址:

https://github.com/ccc013/DataStructe-Algorithms_Study/blob/master/Python/Leetcodes/206_Reverse_Linked_List.py

原文发布于微信公众号 - 算法猿的成长(AI_Developer)

原文发表时间:2019-08-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券