Leetcode 系列 | 反转链表

kbsc13

发布于 2019-08-19 11:26:58

4400

发布于 2019-08-19 11:26:58

文章被收录于专栏：AI 算法笔记

第一时间关注 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 指针，指向其前一个结点，因此肯定需要一个保存前一个结点的变量，也就是反转后链表的头部指针。

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

首先定义一个 prev 保存前一个结点，curr 保存当前结点，然后还有一个 nxt 保存下一个结点，其中 prev 就是最终的反转链表的头结点；
先让 nxt 保存下一个结点；
然后改变 curr 的 next 指针，指向前一个结点，即 prev ;
接着，让 prev = curr ；
最后，就是让 curr = nxt，指向下一个结点
重复 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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-08-16，如有侵权请联系 cloudcommunity@tencent.com 删除

github