• 作者:老汪软件技巧
  • 发表时间: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。