多指针法反转链表(面试常考题)

阳光穿透心脏的1/2处 2022-11-07 13:16 190阅读 0赞

# 一、题目描述 #

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

**示例：**

输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

**提示：**

*  0 <= 节点个数 <= 5000

# 二、思路分析 #

反转链表，就是把每个结点 next 指针的指向给反过来就行了  
需要用到三个指针，它们分别指向**目标结点（cur）**、目标结点的**前驱结点（pre）**、目标结点的**后继结点（next）**。

cur.next = pre：进行反转 。  
next用于指向 cur 原本的后继结点，用于定位下一个结点。

![在这里插入图片描述][20210312131606329.png]

# 三、AC 代码 #

/**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function(head) {
      // 初始化前驱结点为 null
        let pre = null;
        // 初始化目标结点为头结点
        let cur = head;
        while (cur) {
            // 记录next 结点
            let next = cur.next;
            // 反转指针
            cur.next = pre;
            // 记录pre以便后续的反转
            pre = cur;
            // cur往前走一步
            cur = next;
        }
        // 反转结束后，pre 为新的头结点
        return pre
    };

# 四、总结 #

*  处理链表的本质，是处理链表结点之间的指针关系

[本文链接https://blog.csdn.net/qq\_39903567/article/details/114693364][https_blog.csdn.net_qq_39903567_article_details_114693364]

[20210312131606329.png]: /images/20221023/d9096a476c554200b13c740b10bb3da5.png
[https_blog.csdn.net_qq_39903567_article_details_114693364]: https://blog.csdn.net/qq_39903567/article/details/114693364