Leetcode题目206.反转链表(简单)
2024-09-25 14:52:27
题目描述:
反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
思路分析:
方法一:迭代
假设存在链表 1 → 2 → 3 → Ø,我们想要把它改成 Ø ← 1 ← 2 ← 3。
在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用!
代码实现:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public static ListNode reverseList(ListNode head) { //preNode表示当前节点的前一个节点
ListNode preNode = null;
//当前节点curNode
ListNode curNode = head;
while (curNode != null) {
//nextNode,表示当前节点的下一个节点
ListNode nextNode = curNode.next;
curNode.next = preNode;
preNode = curNode;
curNode = nextNode;
}
return preNode;
}
}
时间复杂度:O(n)
空间复杂度:O(1)
思路二:递归
递归的两个条件:
终止条件是当前节点或者下一个节点==null
在函数内部,改变节点的指向,也就是head的下一个节点指向head 递归函数那句
head.next.next = head
很不好理解,其实就是head的下一个节点指向head。
递归函数中每次返回的cur其实只最后一个节点,在递归函数内部,改变的是当前节点的指向。
动画演示如下:
代码实现:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空,或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//这里请配合动画演示理解
//如果链表是 1->2->3->4->5,那么此时的cur就是5
//而head是4,head的下一个是5,下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环,需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur,也就是最后一个节点
return cur;
}
}
最新文章
- linux进程通信
- android 多点
- quartz-2.2.x 快速入门 (1)
- Swift - 使用NSNotificationCenter发送通知,接收通知
- C++中const小结
- linux命令之cat
- poj 2054 Color a Tree(贪婪)
- IntelliJ IDEA 14 注册码生成java代码(转)
- centos快速安装redis
- gdb分析core文件
- MD5加密--Java
- 推荐一款接口 API 设计神器!
- 你不知道的JavaScript --- 作用域相关
- SpringIOC和AOP原理 设计模式
- JS高级 - 面向对象3(面向过程改写面向对象)
- SQL Server-- 存储过程中错误处理
- SQL Server 内存和换页(Paging)
- 牛客网——E进阶吧阶乘
- 3321 Apple Tree 树状数组
- Linux TCP/IP调优参数 /proc/sys/net/目录