剑指 Offer II 024. 反转链表
题目
给定单链表的头节点 head
,请反转链表,并返回反转后的链表的头节点。
示例 1:
输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
示例 2:
输入: head = [1,2]
输出: [2,1]
示例 3:
输入: head = []
输出: []
提示:
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
题解
本题可以使用递归的解法, 链表天然递归的性质,反转链表可以拆分为两个子问题:
- 反转头结点
- 反转头结点后剩下的子节点
而子问题2
求解方式和反转链表一样, 反转头结点后剩下的子节点 又可以拆分为反转头结点
和 反转头结点后剩下的子节点
,依次类推,直到链表只剩下一个节点,
存在的最小子问题是只有一个节点
,可以不用反转, 直接返回。
示例 1:
输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
示例1
的具体执行流程:
首先链表递归,执行递
的过程,递到尾结点, 然后再从尾节点一层一层向上归
,完成反转链表
// 递的过程
1 -> 2 -> 3 -> 4 -> 5 -> null
2 -> 3 -> 4 -> 5 -> null
3 -> 4 -> 5 -> null
4 -> 5 -> null
5 -> null
// 归的过程
// 有两个节点,当前head = 2, 把head.next.next = head, head.next = null
// 即 5-> 4 -> 3 -> 2 -> 1
null <- 1 <- 2 <- 3 <- 4 <- 5
// 有两个节点,当前head = 2, 把head.next.next = head, head.next = null
// 即 5-> 4 -> 3 -> 2
2 <- 3 <- 4 <- 5
// 有两个节点,当前head = 3, 把head.next.next = head, head.next = null
// 即 5-> 4 -> 3
3 <- 4 <- 5
// 有两个节点,当前head = 3, 把head.next.next = head, head.next = null
// 即 5-> 4
4 <- 5
//只有一个节点不反转
5 -> null
代码
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (head == null || head.next == null) {
return head;
}
let newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};
原题链接
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfkgkaf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13