北京网站制作公司飞沐,唐山 建设工程信息网站,手机网页编程,织梦网站地图自动更新题目描述
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a; 输入#xff1a; head [1,2,3,4,5]
输出#xff1a; [5,4,3,2,1]示例 2#xff1a; 输入#xff1a; head [1,2]
输出#xff1a; [2,1]示例 3#…题目描述
给你单链表的头节点 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
分析解答
先说整体思路既然要翻转也就是指针的指向改变。那么就可以让后一个指向自身自身再指向null。
而且每一个节点都是相同的操作直接使用递归即可解决。
结束条件是head null || head.next null。代码如下
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
function ListNode(val, next) {this.val (valundefined ? 0 : val)this.next (nextundefined ? null : next)
}
/*** param {ListNode} head* return {ListNode}*/
var reverseList function(head) {if (head null || head.next null) return headlet result reverseList(head.next)head.next.next headhead.next nullreturn result
};思路拓展
上面使用了递归的操作。下面我们讲讲使用双指针的写法。 双指针 pre 和 cur不断移动 pre 和 cur使得 cur 指向 pre。temp 的作用是防止 cur.next 丢失。
注意要移动 pre否则 cur 的值会发生改变。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
function ListNode(val, next) {this.val (valundefined ? 0 : val)this.next (nextundefined ? null : next)
}
/*** param {ListNode} head* return {ListNode}*/
var reverseList function(head) {let pre nulllet cur headwhile (cur) {let temp cur.nextcur.next prepre curcur temp}return pre
};
