数据结构与算法（六）链表：双指针、双链表

àì夳堔傛蜴生んèń 2023-01-06 01:13 216阅读 0赞

# 链表——双指针和双链表 #

## 1 双指针 ##

> 双指针的思想在链表和数组中的题目都经常会用到，主要是利用两个或多个不同位置的指针，通过速度和方向的变换解决问题。

*  两个指针从不同位置出发：一个从始端开始，另一个从末端开始；
 *  两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。

对于单链表，因为我们只能在一个方向上遍历链表，所以第一种情景可能无法工作。然而，第二种情景，也被称为慢指针和快指针技巧，是非常有用的。

### 1.1 两个链表的第一个公共节点 ###

#### 题目 ####

输入两个链表，找出它们的第一个公共结点。

#### 思路 ####

*  1.先找到两个链表的长度`length1`、`length2`
 *  2.让长一点的链表先走`length2-length1`步，让长链表和短链表起点相同
 *  3.两个链表一起前进，比较获得第一个相等的节点
 *  时间复杂度`O(length1+length2)` 空间复杂度`O(0)`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center]

#### 代码 ####

### 1.2 链表倒数第k个节点 ###

简单思路： 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

优化：

设定两个节点，间距相差k个节点，当前面的节点到达终点，取后面的节点。

前面的节点到达k后，后面的节点才出发。

代码鲁棒性： 需要考虑head为null，k为0，k大于链表长度的情况。

#### 代码 ####

### 1.3 相交链表 ###

#### 题目 ####

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 1]

在节点 c1 开始相交。

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 2]

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
    输出：Reference of the node with value = 8
    输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

#### 思路 ####

##### 1.暴力法 #####

对于链表 A 的每个节点，都去链表 B 中遍历一遍找看看有没有相同的节点。

**复杂度**

*  时间复杂度：O(M \* N)*O*(*M*∗*N*), M, N 分别为两个链表的长度。
 *  空间复杂度：O(1)*O*(1)。

##### 2. 哈希表 #####

*  先遍历一遍链表 A，用哈希表把每个节点都记录下来(注意要存节点引用而不是节点值)。
 *  再去遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点。

**复杂度**

*  时间复杂度：O(M + N)*O*(*M*\+*N*), M, N 分别为两个链表的长度。
 *  空间复杂度：O(N)*O*(*N*)，N 为链表 A 的长度。

##### 3.双指针 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 6]

**如果链表有交点**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 8]

**如果链表没有交点**

两个链表长度一样，第一次遍历结束后 pA 和 pB 都是 null，结束遍历  
两个链表长度不一样，两次遍历结束后 pA 和 pB 都是 null，结束遍历

**复杂度**

*  时间复杂度：O(M + N)*O*(*M*\+*N*), M, N 分别为两个链表的长度。
 *  空间复杂度：O(1)*O*(1)。

#### 代码 ####

##### 1.暴力法 #####

##### 2.哈希表 #####

##### 3.双指针 #####

## 2 双向链表 ##

> 双链还有一个引用字段，称为`prev`字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

### 2.1 扁平化多级双向链表 ###

#### 题目 ####

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

**示例 1：**

输入：head =[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
    输出：[1,2,3,7,8,11,12,9,10,4,5,6]

解释：  
输入的多级列表如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 9]

扁平化后的链表如下图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 10]

**如何表示测试用例中的多级链表？**

以 **示例 1** 为例：

1---2---3---4---5---6--NULL
             |
             7---8---9---10--NULL
                 |
                 11--12--NULL

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
    [7,8,9,10,null]
    [11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
    [null,null,7,8,9,10,null]
    [null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

### 思路 ###

*  遇到child就递归, 把next和child都传递过去, 因为指针会遍历到后面, 正好可以拼接next和child
 *  递归返回之后要清掉child, 并且处理好prev指针

### 代码 ###

// 优化前
    const flatten = (head, next) => { 
      let curr = head
      while (curr && (curr.next || curr.child)) { 
        if (curr.child) { 
          curr.next = flatten(curr.child, curr.next)
          curr.child = null
          curr.next.prev = curr
        }
        curr = curr.next
      }
      if (next) { 
        next.prev = curr
        curr.next = next
      }
      return head
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/90eb0298618d4806a6b1ebd7bea9b31d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/9aa65e89b1084b43b99b29d2ba04b83a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210113144531401.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210113144545519.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2021011314455649.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210113144605726.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210113144614862.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20210113144625549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20210113144636235.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20210113144650457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20210113144701466.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4Njc1Ng==,size_16,color_FFFFFF,t_70#pic_center