欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

【图解算法】链表（下）

程序员文章站 2022-07-14 15:19:47
...

笔试时，链表的题能过尽快过，不考虑空间复杂度；面试时，则尽量考虑如何将空间复杂度降到O(1)。

问题描述

  1. 将单向链表按某值划分成左边小、中间相等、右边大的形式。
  2. 复制含有随机指针节点的链表。
  3. 两个单链表相交的系列问题。

##将单向链表按某值划分成左边小、中间相等、右边大的形式

这道题实际上就是荷兰国旗问题的单链表版本，所谓荷兰国旗问题：（leetcode中的颜色分类问题）

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

实际上，这里是0、1、2或者是随便给一些数字+一个阈值K，小于K的放左边，大于K的放右边，二者是一样的。

注意:
不能使用代码库中的排序函数来解决这道题。且空间复杂度为O(1)。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

这道题如果知道怎么做，那么一个直观的做法就是先将链表存储在一个节点数组中，然后使用数组版本的荷兰国旗解法解决，然后再重新连接成链表，但是这样需要一个O(N)的空间复杂度，推荐在笔试过程中使用该方法快速过掉这道题；在面试中，我们则应该尽量优化，体现我们的思考深度。一个是使用O(1)的空间复杂度，另一个则是保持链表原来的相对顺序。

荷兰国旗问题解法

这里我们先来说下荷兰国旗怎么解，首先要注意，我们使用的是数组；我们只需三个变量来记录数组中的位置，left、right记录分割的位置（整个数组需要划分为三个部分），使用index记录扫描到的数组元素位置。

【图解算法】链表（下）

从上图中可以看到，left = -1、index = 0、right = arr.length。

接下来我们将对index向右进行遍历，每次遍历需要注意一些条件，如果当前的值arr[index]小于K，说明这个值应该放左边区域，如果arr[index]大于K，说明这个值应该放右边，我们来看下代码就很容易明白：

辅助函数：交换数组中的值

void swap(int *arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

排序代码：

void colorSort(int *arr, int len, int K) { // 荷兰国旗问题排序
    int left = -1;
    int right = len;
    int index = 0;
    while (index < right) {
        if (arr[index] < K) { // 当前值小于阈值 K
            swap(arr, ++left, index++);
        } else if (arr[index] > K) { // 当前值大于阈值 K
            swap(arr, --right, index);
        } else { // 当前值等于阈值 K
            index++;
        }
    }
}

理解了荷兰国旗问题，再来理解我们的单链表版本就好理解很多了，事实上，除了使用额外的数组空间外，我们可以使用几个变量来解决这个问题。

单链表版本的荷兰国旗问题

我们可以考虑使用三对Head和End来记录三个区域的链表的头和尾，如下图所示：

【图解算法】链表（下）

如上图所示，我们利用上述的六个变量，将一个单链表分成三个链表，最后将它们串起来：

【图解算法】链表（下）

好，我们知道最终结果长啥样后，接下来就是考虑如何得到这样的结果，实际上代码思路很简单，首先遍历一次链表，用三个head指针分别标记第一个小于K、第一个等于K、和第一个大于K的数的指针，当然，我们要处理边界问题，比如这里面没有等于K的，那么中间的链表就是空的，连接的时候就要十分注意。

代码：

ListNode *colorSort(ListNode *head, int K) {
    ListNode *leftHead = nullptr, *leftEnd = nullptr;
    ListNode *midHead = nullptr, *midEnd = nullptr;
    ListNode *rightHead = nullptr, *rightEnd = nullptr;
    ListNode *next = nullptr;
    while (head != nullptr) { // 将一个链表拆分为三个链表
        next = head->next; // 保存下一个节点
        head->next = nullptr;
        if (head->val < K) {
            if (leftHead == nullptr) {
                leftHead = head;
                leftEnd = head;
            } else {
                leftEnd->next = head;
                leftEnd = leftEnd->next;
            }
        } else if (head->val > K) {
            if (rightHead == nullptr) {
                rightHead = head;
                rightEnd = head;
            } else {
                rightEnd->next = head;
                rightEnd = rightEnd->next;
            }
        } else {
            if (midHead == nullptr) {
                midHead = head;
                midEnd = head;
            } else {
                midEnd->next = head;
                midEnd = midEnd->next;
            }
        }
        head = next;
    }

    // 连接左链表和中间的链表
    if (leftEnd != nullptr) {
        leftEnd->next = midHead;
      	// 如果中间链表为空，midEnd 应指向 leftEnd
        midEnd = (midEnd == NULL) ? leftEnd : midEnd;
    }
    // 连接中间链表和右链表
    if (midEnd != nullptr) {
        midEnd->next = rightHead;
    }
    // 返回三个链表串起来后的头节点
    return (leftHead != NULL) ? leftHead : ((midHead != NULL) ? midHead : rightHead);
}

可以看到，虽然思路简单，但是整个代码细节非常多，面试过程中一不小心就会出错，大家写代码前一定要捋清后再写。

复制含有随机指针节点的链表

【题目】 一种特殊的链表节点类描述如下：

struct ListNode {
    int val;
    ListNode *next; // 和普通的单链表一样
    ListNode *rand; // 随机指向某个节点

    ListNode(int x) : val(x), next(nullptr), rand(nullptr) {}
};

rand指针是这种链表中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向NULL。 给定一个由含有随机指针节点的链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。

进阶：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N) 内完成原问题要实现的函数。

【题意解析】

我们首先画个图来理解一下这种含有随机指针节点的链表：

【图解算法】链表（下）

如上图所示，黄线即为rand指针的指向，可以看到指向是完全随机没有规律的。

【普通解法】

接下来我们说说简单的解法，以节点1为例子，我们知道它的rand指针指向节点2，但是拷贝后的新节点1如何找到新节点2呢？这里我们就会想到使用哈希表，我们可以将 <节点，新节点> 的映射结构存入哈希表中。

我们首先遍历一遍链表，拷贝一份只复制了next指针的链表，同时建立哈希表；再对这个新链表进行一次遍历，每遍历一个节点，将这个节点在哈希表中对应的节点取出，用rand指针去连接即可。

我们先来看看单纯的拷贝单链表：

ListNode *copyByHash(ListNode *head) {
    ListNode *newHead = new ListNode(head->val);
    ListNode *q = newHead;
    ListNode *p = head;
    while (p->next != nullptr) { // 拷贝单链表
        p = p->next;
        q->next = new ListNode(p->val);
        q = q->next;
    }
    return newHead;
}

接下来我们加入哈希表部分：

ListNode *copy(ListNode *head) {
  	if (head == nullptr) { // 空指针判断
        return nullptr;
    }
    ListNode *newHead = new ListNode(head->val);
    ListNode *q = newHead;
    ListNode *p = head;
    map<ListNode *, ListNode *> nodeMap;
    nodeMap[head] = newHead;

    while (p->next != nullptr) { // 拷贝单链表
        p = p->next;
        q->next = new ListNode(p->val);
        q = q->next;
        nodeMap[p] = q; // 第一次遍历的过程中即可同时进行哈希映射
    }
    p = head;
    q = newHead;
    while (q != nullptr) { // 拷贝 rand 指针
        q->rand = p->rand == nullptr ? nullptr : nodeMap[p->rand];
        q = q->next;
        p = p->next;
    }

    return newHead;
}

使用哈希表的方法固然简单，但需要O(N)的空间复杂度，有没有O(1)的解决办法呢？继续看我们的优化方法。

【空间优化】

实际上，我们的解题关键就是节点和新节点之间的联系，假如我们可以使用某种方法将它们联系起来，那么也就不需要哈希表了。这种办法就是将新节点连接在原节点后面，这样通过节点->next就可以获取到新节点了。如下图所示：

【图解算法】链表（下）

我们首先通过一次遍历达成上述效果：

蓝色箭头处为cur->next的指向变更

【图解算法】链表（下）

将图结合代码看更加直观：

ListNode *cur = head;
ListNode *next = nullptr;

while (cur != nullptr) { // 拷贝单链表
    next = cur->next;
    cur->next = new ListNode(cur->val);
    cur->next->next = next;
    cur = next;
}

接下来，在拷贝rand指针的时候，我们只需要拷贝节点->rand->next即可：

【图解算法】链表（下）

cur = head;
ListNode *curCopy = nullptr;
while (cur != nullptr) { // 拷贝 rand 指针
    next = cur->next->next;
    curCopy = cur->next;
    curCopy->rand = cur->rand == nullptr ? nullptr : cur->rand->next;
    cur = next;
}

最终还需要对它们进行拆分：

【图解算法】链表（下）

完整代码：

ListNode *copy(ListNode *head) {
    if (head == nullptr) { // 边界判断
        return nullptr;
    }
    ListNode *cur = head;
    ListNode *next = nullptr;

    while (cur != nullptr) { // 拷贝单链表
        next = cur->next;
        cur->next = new ListNode(cur->val);
        cur->next->next = next;
        cur = next;
    }
    cur = head;
    ListNode *curCopy = nullptr;
    while (cur != nullptr) { // 拷贝 rand 指针
        next = cur->next->next;
        curCopy = cur->next;
        curCopy->rand = cur->rand == nullptr ? nullptr : cur->rand->next;
        cur = next;
    }
    ListNode* res = head->next;
    cur = head;
    while (cur != nullptr) { // 拆分并还原
        next = cur->next->next;
        curCopy = cur->next;
        cur->next = next;
        curCopy->next = next == nullptr ? nullptr : next;
        cur = next;
    }
    return res;
}

两个单链表相交的系列问题

【题目】 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数， 如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null 即可。

【 要求】如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)。

【题意解析】

注意了，本题实际上将链表相交的常见问题都糅合在一起了，是有一定难度的，我们需要先将问题切分开来：

  1. 如何判断单链表有环无环？

    我们写一个函数来实现返回一个链表的环判定，有环返回入环的第一个点，无环则返回null；

  2. 如何判断单链表相交与否？

    这个需要分开讨论，需要意识到，一个链表有环 ，另一个链表无环，是不可能相交的。

    • 两个链表都无环
    • 两个链表都有环

【图解算法】链表（下）

对于有环相交2，我们在返回环的起点的时候，从两个起点中任意返回一个即可。

判断单链表有环无环？

这里也是用到我们前面讲过的快慢指针，如果快慢指针有机会相等，那说明这个链表有环，两个指针在环里面兜圈，否则，任何一个指针到达了NULL，说明这个链表无环。这里理解了后，我们再考虑如何返回入环的第一个节点。

如下方的代码：

  1. 不要忘了处理边界，要形成环至少有三个节点；
  2. 第一次循环中，如果快指针遇到了null，说明链表无环，直接返回null即可；如果快指针和慢指针相遇，即可确定链表有环，接下来就是确定环的入口（或起点）；
  3. 在第二次循环中，我们先将快指针重新指向头节点，然后从一次走两步变为一次走一步，当快慢指针再次相遇时，相遇的节点必然是环的入口节点。

关于第三点，我们如何证明呢？

如下图所示，整个链表的长度为L，其中环部分的长度为R，非环的部分长度为x，当快慢指针相遇时，相遇点到入环节点的距离为y，假设相遇时慢指针走的距离为s，所以s = x + y；同时，对于快指针来说，快指针的速度是慢指针的2倍，我们假设了慢指针走了s，那么快指针就走了2s，且快指针走的距离等价于s加上比慢指针在环中多走了n圈，所以2*s = s + n*R，化简得到s = n * R；另外，整个链表的长度等价于非环部分的长度x加上环的长度R。

我们根据上述得到的三条式子进行代换，可以得到下图中x = (n-1)*R + L-x-y，这条式子表明，我们将快指针重新放到起点，慢指针则不变，快指针从非环部分移动的距离x等价于慢指针从第一次相遇点再次到达入环点的距离(n-1)*R + L-x-y。其中的(n-1)*R表明在这个过程中，慢指针可能会在环中转n-1圈，但不影响快慢指针同时到达入口点；

【图解算法】链表（下）

ListNode *getCircleEntry(ListNode *head) {
    // 处理边界，至少要有三个点才能有环
    if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
        return nullptr;
    }
    ListNode *slow = head->next;
    ListNode *fast = head->next->next;
    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) { // 遇到 null，说明无环
            return nullptr;
        }
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = head; // 快指针回到头节点，慢指针不变
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next; // 快指针每次只走一步
    }
    return fast;
}

如何判断单链表相交与否？

我们根据前面判断有无环的函数，可以将单链表相交问题分为两个部分进行讨论：

ListNode *getIntersectNode(ListNode *head1, ListNode *head2) {
    ListNode *p1 = getCircleEntry(head1);
    ListNode *p2 = getCircleEntry(head2);
    if (p1 == nullptr && p2 == nullptr) {
      // 两个无环单链表相交问题
    } else if (p1 != nullptr && p2 != nullptr) {
      // 两个有环单链表相交问题
    }
}

接下来我们看如何解决无环单链表的相交问题：

  1. 先各自遍历两个链表，记录长度，同时判断最后一个节点是否相等，若不等，则一定不相交，返回null，否则，二者相交，到下一步；
  2. 将链表1的长度记录为len1，将链表2的长度记录为len2，如果len1大于len2，那么链表1先移动len1-len2步，然后两个指针一起走，判断两个指针是否相等，相等返回当前节点即可。
  3. 在第二点的基础上，我们可以做一个小优化，使用一个变量count来记录二者的长度差值，对链表1，每次自增，对链表2，每次自减，即可根据最终count的正负来判断链表1、2何者更长。
ListNode *getNoLoopNode(ListNode *head1, ListNode *head2) {
    ListNode *p = head1;
    ListNode *q = head2;
    int count = 0;
    while (p->next != nullptr) { // 计算链表1长度
        count++;
        p = p->next;
    }
    while (q->next != nullptr) { // 计算链表2长度
        count--;
        q = q->next;
    }
    if (p != q) {
        return nullptr;
    }
    p = count > 0 ? head1 : head2; // 将较长的链表赋给 p
    q = count > 0 ? head2 : head1; // 将较短的链表赋给 q
    
    for (int i = 0; i < abs(count); ++i) { // 因为 p 较长，所以移动 p
        p = p->next;
    }

    while (p != q) { // 直到找到第一个 p 和 q 相等的节点
        p = p->next;
        q = q->next;
    }
    return p;
}

接下来，我们看如何解决有环链表的相交问题：

我们前面已经得到了获取一个有环链表的入环节点的函数：getCircleEntry(ListNode *head)，因此我们可以获取两个链表的入环节点loop1和loop2；

如果loop1 == loop2，说明是第一种有环相交：

【图解算法】链表（下）

我们只需要把前面的判断无环链表的相交节点的函数的边界从null改为loop1/loop2即可：

if (loop1 == loop2) {
    ListNode *p = head1;
    ListNode *q = head2;
    int count = 0;
    while (p->next != loop1) { // 计算链表1长度
        count++;
        p = p->next;
    }
    while (q->next != loop2) { // 计算链表2长度
        count--;
        q = q->next;
    }
    p = count > 0 ? head1 : head2; // 将较长的链表赋给 p
    q = count > 0 ? head2 : head1; // 将较短的链表赋给 q

    for (int i = 0; i < abs(count); ++i) { // 因为 p 较长，所以移动 p
        p = p->next;
    }

    while (p != q) { // 直到找到第一个 p 和 q 相等的节点
        p = p->next;
        q = q->next;
    }
    return p;
}

如果loop1 != loop2，那么两个有环链表有可能不相交，也可能如第二种有环相交情况所示：

【图解算法】链表（下）

解决办法：

我们让链表1从loop1的位置开始行动，如果在再次回到loop1的过程中没有遇到loop2，说明两个链表不相交，直接返回null，否则，返回loop1或者loop2都可以。

else {
    ListNode *p = loop1->next;
    while (p != loop1) {
        if (p == loop2) {
          	return loop2;
        }
        p = p->next;
    }
    return nullptr;
}

整合之后：

ListNode *getLoopNode(ListNode *head1, ListNode *head2) {
    ListNode *loop1 = getCircleEntry(head1);
    ListNode *loop2 = getCircleEntry(head2);
    if (loop1 == loop2) {
        ListNode *p = head1;
        ListNode *q = head2;
        int count = 0;
        while (p->next != loop1) { // 计算链表1长度
            count++;
            p = p->next;
        }
        while (q->next != loop2) { // 计算链表2长度
            count--;
            q = q->next;
        }
        p = count > 0 ? head1 : head2; // 将较长的链表赋给 p
        q = count > 0 ? head2 : head1; // 将较短的链表赋给 q

        for (int i = 0; i < abs(count); ++i) { // 因为 p 较长，所以移动 p
            p = p->next;
        }

        while (p != q) { // 直到找到第一个 p 和 q 相等的节点
            p = p->next;
            q = q->next;
        }
        return p;
    } else {
        ListNode *p = loop1->next;
        while (p != loop1) {
            if (p == loop2) {
                return loop2;
            }
            p = p->next;
        }
        return nullptr;
    }
}

主函数：

ListNode *getIntersectNode(ListNode *head1, ListNode *head2) {
    ListNode *p1 = getCircleEntry(head1);
    ListNode *p2 = getCircleEntry(head2);
    if (p1 == nullptr && p2 == nullptr) { // 两个无环单链表相交问题
        return getNoLoopNode(head1, head2);
    } else if (p1 != nullptr && p2 != nullptr) { // 两个有环链表相交问题
        return getLoopNode(head1, head2);
    }
}

【优化】

我们前面求两个无环单链表的相交节点时，先各遍历一遍得到长度，再遍历第二次去获取位置，实际上我们可以使用更加简洁的写法：

ListNode *getNoLoopNode2(ListNode *head1, ListNode *head2) {
    if (head1 == nullptr || head2 == nullptr)
        return nullptr;

    ListNode *p = head1;
    ListNode *q = head2;
    while (p != q) {
        if (p == nullptr)
            p = head2;
        else
            p = p->next;

        if (q == nullptr)
            q = head1;
        else
            q = q->next;
    }
    return p;
}

原理如下图所示：

p点从带圆圈的橙线（上面那条）出发，到达NULL之后跳转到head2继续，而q从带圆圈的蓝线（下面那条）出发，达到NULL之后跳转到head1继续，二者会在相交处相遇，此时p == q，跳出循环，返回p，即当前的相交节点。

这种方法在两个链表长度相同时，只需遍历相交前的部分即可。

【图解算法】链表（下）

在loop1 == loop2中整合该方法也非常容易，跟之前的方法一样，将对NULL的判断改为对loop1/loop2的判断即可。

相关标签： 高频面试题

上一篇： win10+anaconda+python3.7安装opencv

下一篇： Hadoop分布式文件系统HDFS的安装

推荐阅读