局部反转链表(面试常考题)

本是古典何须时尚 2022-11-07 13:16 154阅读 0赞

# 一、题目描述 #

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

**说明：**

*  1 ≤ m ≤ n ≤ 链表长度。

**示例：**

输入: 1->2->3->4->5->NULL, m = 2, n = 4
    输出: 1->4->3->2->5->NULL

# 二、思路分析 #

局部反转链表是反转链表的升级版。

## 反转链表 ##

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

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

![image.png][]

## 局部反转链表 ##

局部反转需要额外注意的是，链表区间反转完之后，将其拼接上原链表的操作。

用**leftHead**指向整个 反转区间链表的**前驱结点**  
**start** 指向反转区间的**第一个结点**，也是反转后的**最后一个结点**  
**pre**正好指向反转后的区间链表的**第一个结点**  
**cur**正好指向区间链表的**后驱结点**

![image.png][image.png 1]

# 三、AC 代码 #

/**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} left
     * @param {number} right
     * @return {ListNode}
     */
    var reverseBetween = function(head, left, right) {
    // 定义pre、cur，用leftHead来承接整个区间的前驱结点
        let pre,cur,leftHead
        // 用上从大佬那学来的dummy技巧
        const dummy = new ListNode()  
        // dummy后继结点是头结点
        dummy.next = head
        // p是一个游标，用于遍历，最初指向 dummy
        let p = dummy  
        // p往前走 m-1 步，走到整个区间的前驱结点处
        for(let i=0;i<left-1;i++){
            p = p.next
        }
        // 缓存这个前驱结点到 leftHead 里
        leftHead = p
        // start 是反转区间的第一个结点
        let start = leftHead.next  
        // pre 指向start
        pre = start
        // cur 指向 start 的下一个结点
        cur = pre.next
        // 对区间里的链表进行反转
        for(let i=left;i<right;i++){
            let next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        }
        //  leftHead 的后继结点此时为反转后的区间的第一个结点
        leftHead.next = pre
        // 将区间内反转后的最后一个结点 next 指向 cur
        start.next=cur
        // dummy.next 永远指向链表头结点
        return dummy.next
    };

# 四、总结 #

*  处理链表的本质，是处理链表结点之间的指针关系
 *  局部反转链表要注意的是反转完局部链表后的拼接操作

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

[image.png]: /images/20221023/7eb389203f9642369d13b70418501e7f.png
[image.png 1]: /images/20221023/ce0c54ad9af540e986db1a21b23205fd.png
[https_blog.csdn.net_qq_39903567_article_details_114693876]: https://blog.csdn.net/qq_39903567/article/details/114693876