美柑の部屋

涙は見せないと誓った。

Loading…

面试常见问题盘点：链表

链表是面试中经常被问到的一种数据结构，一是因为它实现简单，二是因为它的实现中涉及到指针操作，而一个人对指针操作的熟练程度很能够体现他的C++程序设计水平。这篇文章就来简单地盘点一下面试中经常会被问到的一些链表方面的问题。

一、删除一个给定的链表结点

问题：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)的平均时间复杂度内删除该结点。
在链表中删除一个结点，我们需要知道该结点前驱结点的指针。但是现在只给出指向该结点的指针，又限定了O(1)的平均时间复杂度，所以不能通过遍历的方式找到其前驱结点。这个时候就需要我们跳出常规的思路：我们可以直接用该结点的后继结点的值覆盖掉该结点的值，然后将其后继结点删除。
当然这种方法有一个前提，就是该结点不是链表的最后一个结点。如果是的话，我们只好乖乖地采用正常的方法，从链表头开始遍历找到该结点的前驱结点了。
我们可以计算一下算法的平均时间复杂度：假设链表中有n个结点，我们的算法复杂度为1的概率为(n-1)/n，复杂度为n的概率为1/n，所以平均复杂度仍然为O(1)，满足要求。
总结：这个题主要考察我们打破常规思维的能力，以及对“平均时间复杂度”的理解。

二、在一趟遍历内找到链表的中点

问题：给定单向链表的头指针，要求在一趟遍历内找到链表的中点。
通常情况下，我们会先进行一趟遍历，计算链表的长度n，然后再进行一趟遍历，返回第n/2个结点。
更加快速的解法是利用快慢指针，我们定义两个指针slow和fast用于遍历链表，每次迭代，快指针fast向前走两步，慢指针slow向前走一步。这样，当fast走到链表尾端时，slow指针正好指向链表的中点。

三、判断链表是否存在环

问题：给定单向链表的头指针，判断该链表是否存在环。
仍然是使用快慢指针的方法，定义两个指针slow和fast。如果该链表不存在环，fast走到链表尾端，值会变为NULL；如果该链表存在环，slow和fast最终会相遇。

扩展1：如何知道环的长度（即位于环中的结点个数）？
记录下slow和fast相遇的位置p，令slow和fast继续从p位置移动。我们知道，它们最后还是会在p处相遇，此时slow走了一圈，fast走了两圈。所以，记录slow从p开始移动到再次相遇所走的步数，就是环的长度。

扩展2：如何找出环的入口结点在哪里？
利用两个指针p1和p2，分别从相遇点p和头结点head开始走，每次走一步，最终p1和p2肯定会相遇，相遇的结点就是环的入口结点。

如何证明？展开

下面的代码以链表头结点作为输入，返回指向环的入口结点的指针。如果链表不包含环，则返回NULL：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

ListNode *detectCycle(ListNode *head) {
    if(!head)
        return NULL;
    if(!head->next)
        return NULL;
    if(!head->next->next)
        return NULL;

    ListNode* p1 = head->next;
    ListNode* p2 = head->next->next;
    while(p1 != p2){
        if(!p2->next || !p2->next->next)
            return NULL;
        p1 = p1->next;
        p2 = p2->next->next;
    }

    //一个从相遇点走，一个从起点走，二者相遇的地方即为环的起始点：
    p1 = head;
    while(p1 != p2){
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

扩展3：如何求出带环链表的总长度？
之前已经求出入口结点距离链表头的长度，以及链表环的长度，二者相加，就是带环链表的总长度。

四、求两个链表的交点

问题：给定两个单向链表的头指针，返回指向它们的交点的指针，如果它们没有交点，则返回NULL。（先假设两个链表都没有环。）
方法一：将一个链表的头结点接到另外一个链表尾节点的后面，然后判断得到的新链表是否有环。如果有环，说明原来的链表有交点。
方法二：定义两个指针p1和p2，分别指向第一个链表的头和第二个链表的头，然后每次向前走一格。当p1变为NULL时，将p1重置为第二个链表的头，继续遍历；当p2变为NULL时，将p2重置为第一个链表的头，继续遍历。这样，p1和p2第一次相遇的地方就是两个链表的交点了。
另外，我们记录p1和p2因为遇到NULL而重置的次数，如果发现已经要进行第二次重置，但两个指针仍然没有相遇，则说明两个链表没有交点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(!headA || !headB)
        return NULL;

    ListNode* p1 = headA;
    ListNode* p2 = headB;
    bool p1Changed = false;
    bool p2Changed = false;
    while(p1 != p2){
        p1 = p1->next;
        p2 = p2->next;
        if(!p1){
            if(p1Changed)
                return NULL;
            p1 = headB;
            p1Changed = true;
        }
        if(!p2){
            if(p2Changed)
                return NULL;
            p2 = headA;
            p2Changed = true;
        }
    }
    return p1;
}

扩展：如果不保证两个链表没有环，该如何判断？
首先判断两个链表是否有环，如果两个都没有环，直接利用上面的方法判断即可。
如果一个有环一个没有环，那么两个链表肯定没有交点。
如果两个都有环：假设利用快慢指针方法对链表A求得的相遇结点为a，对链表B求得的相遇结点为b。我们知道，a一定在A的环上，b一定在B的环上，关键是判断a和b所处的环是不是同一个环。我们从a开始遍历，直到再次遇到a之前，如果我们能够遇到b，说明a和b在一个环上，也就是A和B有交点；否则说明两个链表的环是单独的环，两个链表没有交点。

五、反向打印链表元素

问题：给定单向链表的头指针，反向打印链表中的所有元素。
对于非递归方式，可以用一个栈来实现，首先遍历链表，将遍历到的元素依次进栈。在遍历完链表之后，弹栈并依次将弹出的元素打印出来。
当然，本问题也可以用递归方式实现。递归方式类似于树的后序遍历，即先打印后继结点，再打印当前结点。递归方式实现的代码如下：

1
2
3
4
5
6
7

void print(ListNode* head){
    if(!head)
        return;

    print(head->next);
    cout << head->val << endl;
}

六、反转链表

问题：给定单向链表的头指针，将该链表反转，并且返回新链表的头指针。
当然，一种方法仍然是利用栈。遍历链表并将遍历到的元素一个一个压入栈，然后将栈中的元素弹出并依照弹出的顺序构造一个新的链表。
但是如果要求不能使用额外空间呢？我们需要对链表进行原地反转操作。我们在调整结点node的next指针时，除了需要知道node本身之外，还需要知道node的前一个结点prev，因为我们需要把结点node的next指针赋值成prev；同时我们还要事先保存结点node原本的下一个结点succ，以防止链表因为node->next被重新赋值而断开。注意这三个变量的相互关系，写出反转链表的迭代形式就很容易了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

ListNode* reverseList(ListNode* head) {
    if(!head || !head->next)
        return head;

    ListNode* prev = head;
    ListNode* node = head->next;
    while(node){
        ListNode* succ = node->next;
        node->next = prev;
        prev = node;
        node = succ;
    }
    return prev;
}

反转链表也可以用递归的形式来实现，其实本质上和树的后序遍历仍然是类似的，即先反转后继结点，再反转当前结点。代码如下：

1
2
3
4
5
6
7
8

ListNode* reverseRecur(ListNode* head){
    if(!head || !head->next)
        return head;
    ListNode* p  = reverseRecur(head->next);
    head->next->next = head;
    head->next = NULL;
    return p;
}
对上述代码的解释展开

评论