链表学习

2016-07-01

字数统计: 3.4k字 | 阅读时长: 13min

链表问题在面试过程中也是很重要也很基础的一部分，链表本身很灵活，很考查编程功底，所以是很值得考的地方。我将复习过程中觉得比较好的链表问题整理了下。

下面是本文所要用到链表节点的定义：

struct ListNode {
    int data;
    ListNode *next;
};

1. 在O(1)时间删除链表节点

题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。

分析：在链表中删除一个结点，最常规的做法是从链表的头结点开始，顺序查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度自然就是O(n) 了。
我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点，由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的。当然，在删除之前，我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为O(1)。

代码如下:

void deleteListNode(ListNode *current) {
    if (current != NULL && current->next != NULL) {
        ListNode *pNext = current->next;
        current->data = pNext->data;
        current->next = pNext->next;
        delete pNext;
    }
}

2. 反转单链表

题目描述：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

分析：假设有链表A->B->C->D->E->F->G。在反转链表过程中的某一阶段，其链表指针指向为：A<-B<-C<-D E->F->G。也就是说在结点D之前的所有结点都已经反转，而结点D后面的结点E开始的所有结点都没有反转。这样D跟E之间存在了断裂。我们如果要实现链表的反转，会有以下几个重要步骤：

D->E变为D->C，指针反转

指针往后移动一个，操作下一个结点E

结合1.2我们发现需要操作3个指针，分别是C,D,E(我们使用p,q,r表示)。
因此可以考虑存储C/D/E三个结点的指针，通过这三个结点的指针实现反转。

我们通过以下图表来说明：

p = head;
q = head->next;

head->next = NULL;

现在进入循环体，这是第一次循环
r = q->next;
q->next = p;

p = q;
q =r;

第二次循环
r = q->next;

q->next = p;

p = q;

q = r;

第三次循环。。。。。

代码如下：

ListNode *ReverseListNode(ListNode *head) {

    if (head == NULL || head->next == NULL)
        return head;

    ListNode *p,*q,*r;

    p = head;
    q = head->next;
    head->next = NULL;

    while (q) {
        r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    head = p;
    return head;
}

3. 求链表的中间节点

题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。

分析：此题可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法，就是通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。

代码如下:

ListNode *MiddleNode(ListNode *head) {

    if (head == NULL)
        return NULL;
    ListNode *slow,*fast;
    slow = fast = head;

    //如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件
    //while(fast && fast->next != NULL && fast->next->next != NULL)
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

4. 判断单链表是否存在环

题目描述：输入一个单向链表，判断链表是否有环？

分析：通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。

代码如下：

bool hasCircle(ListNode *head,ListNode *circleNode) {

    ListNode *slow,*fast;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            circleNode = fast;
            return true;
        }
    }
    return false;
}

5. 找到环的入口点

题目描述：输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？

解题思路：由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。

为什么？：假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有：

p1走的路径： a+b ＝ n；
p2走的路径： a+b+kL = 2n； p2 比 p1 多走了k圈环路，总路程是p1的2倍

根据上述公式可以得到 k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。

显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。

代码如下：

ListNode *findLoopPort(ListNode *head) {

    if (head == NULL || head->next == NULL)
        return NULL;

    ListNode *slow,*fast;
    slow = fast = head;

    // 判断是否存在环
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
            break;
    }
    //不存在环
    if (fast != slow)
        return NULL;
    //快指针从头开始走，步长变为1
    fast = head;
    //两者相遇即为入口点
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

6.编程判断两个链表是否相交

题目描述：给出两个单向链表的头指针（如下图所示），比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。

解题思路：

1.直接循环判断第一个链表的每个节点是否在第二个链表中。但，这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然，我们得找到一种更为有效的方法，至少不能是O（N^2）的复杂度。

2.针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的每个节点是否在hash表出现，如果所有的第二个链表的节点都能在hash表中找到，即说明第二个链表与第一个链表有相同的节点。时间复杂度为为线性：O(Length(h1) + Length(h2))，同时为了存储第一个链表的所有节点，空间复杂度为O(Length(h1))。是否还有更好的方法呢，既能够以线性时间复杂度解决问题，又能减少存储空间？

3.转换为环的问题。把第二个链表接在第一个链表后面，如果得到的链表有环，则说明两个链表相交。如何判断有环的问题上面已经讨论过了，但这里有更简单的方法。因为如果有环，则第二个链表的表头一定也在环上，即第二个链表会构成一个循环链表，我们只需要遍历第二个链表，看是否会回到起始点就可以判断出来。这个方法的时间复杂度是线性的，空间是常熟。

4.进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。
所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N)，空间复杂度为O(1)，显然比解法三更胜一筹。

解法四代码如下:

bool isIntersect(ListNode *head1,ListNode *head2) {

    if (head1 == NULL || head2 == NULL)
        return  NULL;
    while (head1->next != NULL) {
        head1 = head1->next;
    }
    while (head2->next != NULL ) {
        head2 = head2->next;
    }
    if (head1==head2)
        return true;
    else return false;
}

7.链表有环，如何判断相交

题目描述：上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?

分析：如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在于两个链表上。因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。

代码如下：

bool isIntersectWithLoop(ListNode *head1,ListNode *head2) {

    ListNode *circleNode1,*circleNode2;
    //判断链表带不带环，并保存环内节点
    if (!hasCircle(head1, circleNode1))
        return false;
    if (!hasCircle(head2, circleNode2))
        return false;

    ListNode *temp = circleNode2->next;
    while (temp != circleNode2) {
        if (temp == circleNode1)
            return true;
        temp = temp->next;
    }
    return false;
}

8.链表中倒数第k个节点

题目描述：输入一个链表，输出该链表中倒数第k个结点。

为了实现一次遍历链表就能找到倒数第k个结点，我们可以定义两个指针，第一个从链表的头指针开始遍历向前走k-1，第二个指针保持不动，从第K步开始，第二个指针也开始从链表的头指针开始遍历.由于两个指针的距离保持在k-1，当第一个指针到达链表的尾结点时，第二个指针正好是第k个结点.

代码如下:

ListNode *FindthToTail(ListNode *phead,unsigned int k) {

    if (phead == NULL || phead->next == NULL) {
        return NULL;
    }
    ListNode *pFast = phead;
    ListNode *pLow = NULL;

    for (unsigned int i = 0; i<k-1; i++) {
        pFast = pFast->next;
    }

    pLow = phead;

    while (pFast-> next != NULL) {
        pFast = pFast->next;
        pLow = pLow->next;
    }
    return pLow;
}

9.合并两个排序的链表

题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的.

链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点.在剩余的结点中，链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是剩余结点的头结点，把这个结点和之前已经合并好的链表的尾结点链接起来.

代码如下:

ListNode *Merge (ListNode *head1, ListNode *head2) {

    if (head1 == NULL) {
        return head2;
    } else if (head2 == NULL)
        return head1;

    ListNode *mergedHead = NULL;

    if (head1->data < head2->data) {
        mergedHead = head1;
        mergedHead->next = Merge(head1->next,head2);
    } else {
        mergedHead = head2;
        mergedHead->next = Merge(head1,head2->next);
    }
    return mergedHead;
}

10.两个链表的第一个公共结点

题目描述：输入两个链表，找出它们的第一个公共结点.

从链表结点的定义可以看出，这两个链表是单向链表，如果两个单向链表有公共结点，那么这两个链表从某一结点开始，他们的next都是指向同一个结点.但是由于是单向链表的结点，每个结点只有一个next，因此从第一个公共结点开始，之后他们所有结点都是重合的，不可能再出现分叉。

代码如下:

ListNode *FindFirstCommonNode(ListNode *head1, ListNode *head2) {

    // 得到两个链表长度
    unsigned int nLength1 = GetListLength(head1);
    unsigned int nLength2 = GetListLength(head2);
    int nLengthDiff = nLength1 - nLength2;

    ListNode *pListHeadLong = head1;
    ListNode *pListHeadShort = head2;

    if (nLength2 > nLength1) {
        pListHeadLong = head2;
        pListHeadShort = head1;
        nLengthDiff = nLength2 - nLength1;
    }
    // 长链表先走
    for (int i = 0; i<nLengthDiff;i++) {
        pListHeadLong = pListHeadLong->next;
    }

    while (pListHeadLong != NULL && pListHeadShort != NULL && pListHeadShort != pListHeadLong) {
        pListHeadLong = pListHeadLong->next;
        pListHeadShort = pListHeadShort->next;
    }

    ListNode *pCommonNode = pListHeadLong;
    return pCommonNode;
}
// 获取链表长度
unsigned int GetListLength(ListNode *head) {

    unsigned int length = 0;
    ListNode *pNode = head;

    while (head != NULL) {
        length ++;
        pNode = pNode->next;
    }
    return length;
}

本文作者： Aeron_Xie
最后更新： 2023年03月25日 22:39:54
本文链接： http://aeronxie.github.io/post/66ad38b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！