算法详解 | 反转单向链表进阶

亦凉 2022-10-05 07:48 135阅读 0赞

# 算法详解 | 反转单向链表进阶 #

> 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

从定义可以知道，链表的每个元素实际上在内存中并不是连续，只是逻辑上看起来是连续。

## Leetcode题目 ##

给你单链表的头指针 `head` 和两个整数 `left` 和 `right` ，其中 `left` <= `right` 。请你反转从位置 `left` 到位置 `right` 的链表节点，返回 反转后的链表 。

示例 1：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center][]

输入：head = [1,2,3,4,5], left = 2, right = 4
    输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
    输出：[5]

提示：

链表中节点数目为 n
    1 <= n <= 500
    -500 <= Node.val <= 500
    1 <= left <= right <= n

## 解题思路 ##

从提示条件可以知道，`1 <= left <= right <= n` 意味着left是有机会跟head重叠，而上篇文章也提到，单向链表是从头部开始遍历，最重要是确定`head节点`的位置，而尾部节点暂时可以忽略。假如`left` 跟`head`重叠，那就意味着这里的`head`节点也会发生位置变化，而当`head`跟`left`不重叠，则`head`是固定的，接下来我们分两种场景来讨论

### `left`与`head`不重叠 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 1][]

从上图可以看到，这时候变化只有黄色区域部分，而`head`节点是可以保持不变，这时候只需要黄色区域部分进行排序即可，不会影响`head`节点的顺序。这样子我们完全可以对黄色区域使用上一篇文章用到的思路进行排序，然后再用`Left-1`节点指向`Right`节点，`Left`节点指向`Right+1`节点，再返回`head`节点即可

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 2][]

### `left`与`head`重叠 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 3][]

从上图可以看到，此时黄色区域内的节点进行反转，`head`节点也会发生变化，会出现在`1-n`之间，这会导致`head`节点会变得很难判断

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 4][]

### 哨兵节点 ###

解决上面的问题，我们需要想办法让`head`节点的位置变成相对固定，这样以上两种场景都可以使用同一套模型解决。这时候我们可以引入一个自定义固定的哨兵节点（用来追踪`head`节点），让其`next`指针永远都指向`head` 节点，不管`head`节点的位置怎么变化，哨兵节点的`next`永远是指向`head`节点，从而可以确定`head`节点的位置

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 5][]

从上图可以看到，由于哨兵节点`dummy`是我们自己创建的一个虚拟节点，它的位置任何情况下都不会发生变化，不管`head`节点去到哪个位置，它的`next`指针始终指向着`head`节点

dummy.next = head

### 任务分解 ###

从上一篇`反转链表基础版`可以得知，如果我们要操作链表的元素，需要两个指针分别对前后节点进行操作。`Pre` 指向要操作节点的前一个节点，`Cur`指向当前要操作的节点。在这个模型我们需要内外两部分链表操作，一个黄色区域内的部分，一个是黄色区域外的部分，要完成局部链表反转，我们需要利用以下几个指针：

*  `LeftNodePre`: 指向`Left-1` 节点，它的位置不会跟随黄色区域节点反转而发生变化，用来连接反转后的节点
 *  `LeftNodeCur`: 指向`Left`对应节点，它的位置反转后会发生变化，反转后会变成黄色区域中的最后节点，用于连接黄色区域后一个节点
 *  `RightNodePre`: 就是我们上篇的`pre`指针，指向要被操作的节点的前一个节点，它会从`Left`位置一直往后移动，直到移动到`Right`节点结束
 *  `LeftNodeCur`: 就是我们上篇的`cur`指针，指向黄色区域内要被操作的节点，它会从`Left+1`的位置一直往后移动

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 6][]

从上图可以看到，如果想要对局部节点进行遍历，就需要通过以上3个步骤：

1.  先对黄色区域进行内部排序，分别用`RightNodePre` ,`RightNodeCur`来操作前后两个节点
2.  `LeftNodePre`指针对应节点的`next`指针指向`RightNodePre` 指针对应的节点
3.  `LeftNodeCur` 指针对应节点的`next`指针指向`RightNodeCur`指针指向的节点

## 步骤拆解 ##

### 步骤1 ###

创建哨兵节点，让它的`next`指针指向我们的`head`节点，这样我们的`head` 节点就变成已知条件。由于哨兵节点是我们自己定义的一个虚拟节点，所以`Left`肯定不会从哨兵节点开始，只会从它下一个节点位置开始，这就保证了即使`Left`跟`head`重叠，我们依然知道它下一个节点必定是`head`

dummy.next = head;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 7][]

### 步骤2 ###

创建一个`LeftNodePre` 指针，让它head节点开始寻找`Left`节点，并且创建`LeftNodeCur`指针，让它指向`Left`节点

leftNodePre = head;
    //让LeftNodePre指针从第一个节点开始扫，直到扫到第Left-1个节点
    for(int i=1;i<left;i++){ 
      leftNodePre = leftNodePre.next;
    }
    //当前LeftNodePre指针的下一个节点就是Left节点
    leftNodeCur = leftNodePre.next;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 8][]

### 步骤3 ###

创建`RightNodePre`指针，让它指向`Left`节点(因为`RightNodePre`需要从`Left`位置开始挪动，直到`Left->Right`所有节点都遍历完),同时创建`RightNodeCur`指向当前要操作的节点

RightNodePre = LeftNodeCur;
    RightNodeCur = RightNodePre.next;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 9][]

### 步骤4 ###

创建一个临时`Next`指针指向`RightNodeCur`指针对应节点的后一节点，用于`RightNodeCur`指针移动需要。让`RightNodeCur`指向的节点的`Next`指针指向`RightNodePre`节点，然后向后移动`RightNodeCur`和`RightNodePre`指针，重复上一步操作，直到`RightNodePre`指针移动到`right`节点位置结束

for(int i=left;i<right;i++){ 
    //next是临时变量，用于存储当前rightNodeCur下一个节点位置
      next = rightNodeCur.next;
      rightNodeCur.next = rightNodePre;
      rightNodePre = rightNodeCur;
      rightNodeCur = next;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 10][]

### 步骤5 ###

最后，将`LeftNodePre`指针对应的节点的`next`指针指向`RIghtNodePre`指针对应的节点(黄色区域反转后的首节点),`LeftNodeCur`指针指向的节点的`next`指针指向`RightNodeCur`对应的节点，然后此时所有节点已经重新排列，此时的`dummy.next`依然是`head`节点

leftNodePre.next = rightNodePre;
    leftNodeCur = rightNodeCur;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 11][]

### 特殊情况 ###

我们还需要考虑的是当`Head` 是null或者链表元素只有一个的情况，尝试套入模型是否可行，如果不可行则特殊处理。很明显当传进来的`Head`是null或者`left>=Right`，需要特殊处理

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 12][]

## 解决方案 ##

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
    class Solution { 
        public ListNode reverseBetween(ListNode head, int left, int right) { 
           if (null == head || left>=right) { 
                return head;
            }
    
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode leftNodePre  = dummy;
           //寻找Left节点的位置
            for(int i=1;i<left;i++){ 
                leftNodePre = leftNodePre.next;
            }
        
            //创建指针变量用于left相关节点操作
            ListNode leftNode = leftNodePre.next;
            ///创建指针变量用于right相关节点操作
            ListNode rightNodePre = leftNode;
            ListNode rightNodeCur = leftNode.next;
    
            for(int i=left;i<right;i++){ 
                ListNode next = rightNodeCur.next;
                rightNodeCur.next = rightNodePre;
                rightNodePre = rightNodeCur;
                rightNodeCur = next;
            }
            leftNode.next = rightNodeCur;
            leftNodePre.next = rightNodePre;
            
    
            return dummy.next;
        }
    }

执行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 13][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/4abad911e27f4ef69861adc1125859fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/fbb7c89235a54ad7b2e8988471bc5461.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221005/a9f6392c0c474acabd7cd994a902ea6a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221005/4c0c405cb5f94acbbde71db0a054d77c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221005/07d88e1d1e83406ea7bd137a2a6f7bb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221005/51183e63bf3d4dc997e3e2729c1695ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221005/1e6e4e86c9624a84b3296c282658cb40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221005/ca9da942d1544b7c9f5644c81ce1571e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221005/99c485feb6e24ee09025bbc6ac26970f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221005/fccb8454d44d4c6399b97e6b7cafe7aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221005/e54179fe748e40e1b2e9ba06f227427b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221005/db44cb951c5e4f3daebf70e3a19184cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221005/bbd3e0bac1dc401999a9cc55f4411449.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221005/b5920378e8d64694a6fa8076810e5126.png