【Leetcode链表】反转链表(206)
2024-10-08 03:09:37
题目
反转一个单链表。
示例:
输入: 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 = None
# 用三个指针,前一个p,当前c,后一个n
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
c, p = head, None # p初始是Null节点
while c:
# n = c.next # 当前节点后一个
# c.next = p # 重要,当前节点指向后一个
# p = c # 后移前节点,为当前节点c后移做准备
# c = n # 后移当前节点
# 并行,不存在赋值顺序
# So炫酷的写法,劳资只能照着上面式子改,主要还是笨!
c.next, p, c = p, c, c.next
return p
# 时间复杂度O(n),空间复杂度O(1)
# # 递归解法: 时间复杂度O(n),空间复杂度O(n)
# class Solution:
# def reverseList(self, head: ListNode) -> ListNode:
# if head==None or head.next == None:
# return head
# p = self.reverseList(head.next)
# head.next.next = head
# head.next = None
# return p
# # 不妨假设链表为1,2,3,4,5。按照递归,当执行reverseList(5)的时候返回了5这个节点,reverseList(4)中的p就是5这个节点,我们看看reverseList(4)接下来执行完之后,5->next = 4, 4->next = null。这时候返回了p这个节点,也就是链表5->4->null,接下来执行reverseList(3),代码解析为4->next = 3,3->next = null,这个时候p就变成了,5->4->3->null, reverseList(2), reverseList(1)依次类推,p就是:5->4->3->2->1->null
最新文章
- unity调用摄像头的方法
- membership 启用 roleManager 抛出异常:未能加载文件或程序集MySql.Web
- DataTable的筛选,过滤后绑定数据源的两种方法(DataTable的select和使用linq返回List集合)
- sharepoint workflow不能正常使用
- 解决Failed to execute goal org.apache.maven.plugins
- 【原创】FPGA开发手记(三) PS/2键盘
- centos Minicom通信终端
- JavaEE Tutorials (2) - 使用教程示例
- c# in deep 之LINQ简介(1)
- robot framework -记录错误
- java域名解析
- N阶台阶问题(详解)
- Cookie、LocalStorage 与 SessionStorage的区别在哪里?
- JQuery 常用的那些东西
- nginx替换响应内容
- ACA:利用ACA解决TSP优化最佳路径问题——Jason niu
- opencv学习之路(27)、轮廓查找与绘制(六)——外接圆、椭圆拟合、逼近多边形曲线、计算轮廓面积及长度、提取不规则轮廓
- 第 8 章 容器网络 - 062 - 如何使用 flannel host-gw backend?
- python特殊的数据类型
- 上手并过渡到PHP7(3)——Uniform Variable Syntax到底统一了什么