- 作者:老汪软件技巧
- 发表时间:2024-10-07 07:01
- 浏览量:
难度:简单
题目:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
提示:
解题思路:
解这道题,关键是理解链表节点的连接关系以及如何通过改变节点的next指针来实现链表的反转。
初始化:定义三个指针,prev(前一个节点)、curr(当前节点,初始为头节点)和next(下一个节点),用于在反转过程中跟踪和修改节点的连接关系。迭代:使用循环遍历链表,直到当前节点curr变为null,表示到达链表尾部。
3. 处理头节点:遍历结束后,原来的尾节点将成为新的头节点,而原来的头节点将成为新的尾节点。因此,prev将指向新的头节点。
JavaScript实现:
/**
* 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}
*/
function reverseList(head) {
let prev = null; // 前一个节点
let curr = head; // 当前节点
while (curr !== null) {
let next = curr.next; // 保存当前节点的下一个节点
curr.next = prev; // 将当前节点指向前一个节点,完成一次反转
prev = curr; // 前一个节点向后移动
curr = next; // 当前节点向后移动
}
return prev; // 最终prev会指向原链表的尾节点,即新链表的头节点
}
这段代码首先定义了三个指针,并通过循环实现了链表的反转。在每一轮循环中,通过改变节点的next指针方向,逐步将链表由前往后反转。最后,返回新的头节点prev。