专栏首页编程理解Leetcode 206. 反转链表

Leetcode 206. 反转链表

题目描述

反转一个单链表。

示例 1:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

迭代解法

遍历链表,以 cur 表示当前节点,以 last 表示上一个节点,将 cur 的 next 指针指向 last 即可。

# 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:
        last,cur=None,head
        while cur:
            cur.next,cur,last=last,cur.next,cur
        return last

这里使用了 python 的多元赋值,等号右边的值在赋值操作结束前会保持不变。

递归解法

以 reverseList(node) 函数表示 node 节点为头结点的反转链表,则 reverseList(node) 的反转链表为 reverseList(node.next) 尾部追加 node 节点,即 node.next.next = node。

# 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 not head.next:
            return head
        ret=self.reverseList(head.next)
        head.next.next,head.next=head,None
        return ret

在执行 node.next.next = node 后,设置 node.next = None,避免最后两个节点形成循环。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 783. 二叉搜索树结点最小距离

    二叉搜索树属于有序树结构,一个可以利用的特点就是中序遍历可以得到有序数组,得到有序数组后遍历一次即可得到两节点最小差值。

    zhipingChen
  • Leetcode 501. 二叉搜索树中的众数

    给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

    zhipingChen
  • Leetcode 938. 二叉搜索树的范围和

    输入:root = [10,5,15,3,7,null,18], L = 7, R = 15

    zhipingChen
  • Python实现链表

    py3study
  • iOS开发——头像设置及本地沙盒保存,圆形头像显示

    现在的APP中,对于头像的设置,我们大多采用圆形头像,并且需要支持从照相机获取或者从相册中选择用户需要的头像,并且保存在本地或者服务器中。

    Originalee
  • 使用 python 进行微信好友分析

    【特别提醒】:pyecharts 库用的是0.5.x版本,而在 pip 中安装的为1.x.x版本,因此需要自行到【官网】中下载。

    py3study
  • [数据结构与算法] 链表的其他类型

    单链表是最简单的链表,单链表的一种变形就是循环单链表,其中最后一个结点的next域不用None,而是指向表的第一个结点,这样就形成了一种循环结构,所以叫循环单链...

    用户1622570
  • iOS 一个可滑动缩放的轮播图

    Raindew
  • LeetCode 图解 | 206.反转链表

    今天分享的题目来源于 LeetCode 上第 206 号问题:反转链表。这道题目经常出现在算法面试中的笔试环节。

    五分钟学算法
  • 【Leetcode】82. 删除排序链表中的重复元素 II

    给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

    Leetcode名企之路

扫码关注云+社区

领取腾讯云代金券