单链表经常为公司面试所提及,先不贬其过于简单,因为单链表确实是数据结构中最简单的一部分,但往往最简单的,人们越无法把握其细节。本文一共总结了单链表常被提及的各种操作,如下:

  1. 逆序构造单链表;
  2. 链表反转;
  3. 链表排序;
  4. 合并两个有序链表;
  5. 求出链表倒数第 k 个值;
  6. 判断链表是否有环,有环返回相遇结点;
  7. 在一个有环链表中找到环的入口;
  8. 删除当前结点;
  9. 找出链表的中间结点。

本文中的所有操作均针对带有头结点的单链表。请注意:头结点和第一结点是两个结点,百度百科解释为:为方便操作,在单链表的第一个结点之前附设一个结点,称之为头结点。本文中用 header 代替头结点。

在继续下文之前先约定下结点结构:

/* 定义结点结构 */
struct Node
{
    int data;
    Node * next;
    Node() { data = 0; next = nullptr; }
};

/* 定义头结点 */
Node * header = new Node;

具体分析与实现代码

2.1 逆序构造单链表

例如:输入数据:1 2 3 4 5 6,构造单链表:6->5->4->3->2->1。

/* 逆序构造单链表,-1 结束输入 */
void desc_construct(Node * header)
{
    Node * pre = nullptr;  // 前一个结点
    int x;
  
    while (cin >> x && x != -1)
    {
        Node * cur = new Node;
        cur->data = x;
        cur->next = pre;  // 指向前一个结点
        pre = cur;        // 保存当前结点
    }
  
    header->next = pre;  // 头结点指向第一结点
}

2.2 链表反转

例如:假设现有链表:6->5->4->3->2->1,进行反转操作后,链表变成:1->2->3->4->5->6。

/* 反转链表 */
void reverse(Node * header)
{
    if (!header->next || !header->next->next)  // 如果是空链表或链表只有一个结点
        return;
  
    Node * cur = header->next;  // 指向第一个结点
    Node * pre = nullptr;
  
    while (cur)
    {
        Node * temp = cur->next;  // 保存下一个结点
        cur->next = pre;          // 调整指向
        pre = cur;                // pre 前进一步
        cur = temp;               // cur 前进一步
    }
  
    header->next = pre;  // 头结点指向反转后的第一结点
}

2.3 链表升序排序

我们希望用最小的时间复杂度来完成这个排序任务。归并排序是个不错的选择,平均时间复杂度 $T(n)=O(nlogn)$,但是还有其他方法么?

我们想到经常出现的快排,快排是需要一个指针指向头,一个指针指向尾,然后两个指针相向运动并按一定规律交换值,最后使得支点左边小于支点,支点右边大于支点,但是对于单链表而言,指向结尾的指针很好办,但是这个指针如何往前,我们只有一个 next(这并不是一个双向链表)。

如果是这样的话,对于单链表我们没有前驱指针,怎么能使得后面的那个指针往前移动呢?所以这种快排思路行不通,如果我们能使两个指针都往 next 方向移动并且也可以按相同规律交换值那就好了,怎么做呢?

接下来我们使用快排的另一种思路来解答。我们只需要两个指针 i 和 j,这两个指针均往 next 方向移动,移动的过程中始终保持区间 [1, i] 的 data 都小于 base(位置 0 是主元),区间 [i+1, j) 的 data 都大于等于 base,那么当 j 走到末尾的时候便完成了一次支点的寻找。若以 swap 操作即 if 判断语句成立作为基本操作,其操作数和快速排序相同,故该方法的平均时间复杂度亦为 $T(n)=O(nlogn)$。

/**
 * 链表升序排序
 * 
 * begin 链表的第一个结点,即 header->next
 * end   链表的最后一个结点的 next
 */
void asc_sort(Node * begin, Node * end)
{
    if (begin == end || begin->next == end)  // 链表为空或只有一个结点
        return;
  
    int base = begin->data;   // 设置主元
    Node * i = begin;         // i 左边的小于 base
    Node * j = begin->next;   // i 和 j 中间的大于 base
  
    while (j != end)
    {
        if (j->data < base)
        {
            i = i->next;
            swap(i->data, j->data);
        }
        j = j->next;
    }
    swap(i->data, begin->data);  // 交换主元和 i 的值

    asc_sort(begin, i);      // 递归左边
    asc_sort(i->next, end);  // 递归右边
}

// how to use it?
asc_sort(header->next, nullptr);

2.4 合并两个有序的单链表

为简化问题,以下代码为合并两个升序链表。

/* 合并两个有序链表 */
void asc_merge(Node * header, Node * other_header)
{
    asc_sort(header->next, nullptr);  // 保证有序
    asc_sort(other_header->next, nullptr);

    if (!header->next)  // 链表为空
    {
        header->next = other_header->next;  // 合并后两个 header 指向第一个结点
        return;
    }
    if (!list->header->next)  // 链表为空
    {
        other_header->next = header->next;  // 合并后两个 header 指向第一个结点
        return;
    }

    Node * p = nullptr;                         // 还需一个指针,指向合并的结点
    Node * this_pointer = header->next;         // 第一个结点
    Node * other_pointer = other_header->next;  // 第一个结点
    
    // 单独考虑合并的第一个结点
    if (this_pointer->data < other_pointer->data)
    {
        other_header->next = p = this_pointer;  // p 指向新合并的结点
        this_pointer = this_pointer->next;      // 前进一步
    }
    else
    {
        header->next = p = other_pointer;      // p 指向新合并的结点
        other_pointer = other_pointer->next;   // 前进一步
    }

    while (this_pointer && other_pointer)
    {
        if (this_pointer->data < other_pointer->data)
        {
            p->next = this_pointer;  // 合并新结点
            p = this_pointer;        // p 前进一步指向新合并的结点
            this_pointer = this_pointer->next;
        }
        else
        {
            p->next = other_pointer;  // 合并新结点
            p = other_pointer;        // p 前进一步指向新合并的结点
            other_pointer = other_pointer->next;
        }
    }

    // 处理剩下的结点
    if (this_pointer)
        p->next = this_pointer;
    if (other_pointer)
        p->next = other_pointer;
}

2.5 返回链表倒数第 k 个值

例如,给定链表 1->4->3->5->6->8,返回倒数第 3 个数,也就是 5。要求,只给定链表,但并不知道链表长度,如何在最短时间内找出这个倒数第 k 个值。

其实思路很简单,假设 k 是小于等于链表长度,那么我们可以设置两个指针 p 和 q,这两个指针在链表里的距离就是 k,那么后面那个指针走到链表末尾的 nullptr 时,另一个指针肯定指向链表倒数第 k 个值。

/* 返回链表倒数第k个值 */
int kth_last(Node * header, int k)
{
    Node * p = header->next;
    Node * q = p;

    for (int i = 0; i < k; i++)
    {
        if (!q)
        {
            cout << "链表长度小于k\n";
            return -1;
        }
        q = q->next;
    }

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

2.6 判断链表是否有环,有环返回相遇结点

有环是什么意思?一个单链表最后一个结点的位置的 next 应该是 nullptr,标志着链表的结尾,但是如果现在这个 next 指向了链表里的某一个结点(可以是自身),那么这个链表就存在环。如下图:

因此我们只要找到两个结点,其地址相同(因为两个结点的 data 可能相同),即可断定有环。

我们的思路就是:设置两个快慢指针(快慢指针即两个指针起点相同,慢指针每次走一步,快指针走两步),让它们一直往下走,直到它们相等,说明有环。下面简单证明,

如上图,A 为链表第一个结点,B 为环与链表的交叉点,C 为快慢指针相遇的位置。假设环的长度为 r,则有

$$ \frac {AB+BC+n_1r}{2}=AB+BC+n_2r\tag{左为快指针,右为慢指针} $$

其中,r 为正整数(即 1,2,3...),AB、BC 为非负整数(即 0,1,2,3...),n1 和 n2 分别为快指针、慢指针走的圈数,也为非负整数。接着化简为:

$$ AB+BC=(n_1-2n_2)r $$

一个有环的单链表,其 AB 和 r 是固定的,所以只要使 n1 和 n2 变化至使 BC 能满足是一个非负整数的条件即可。

仔细观察上式,我们发现,C 点一定是唯一的。

$$ BC=nr-AB \tag{其中 $n=n_1-2n_2$} $$

这个证明很简单。对于任意两个满足条件的不同的 n 值,一小一大,相比较而言,它们计算出的两个 BC 值的差值一定是整除 r 的,所以 C 点必定唯一。

/* 判断链表是否有环,有环返回相遇结点,无环返回 nullptr */
Node * is_loop(Node * header)
{
    if (!header->next)  // 空链表
        return nullptr;
  
    Node * slow_pointer = header;
    Node * fast_pointer = header;
  
    while (fast_pointer->next && fast_pointer->next->next && slow_pointer != fast_pointer)
    {
        slow_pointer = slow_pointer->next;        // 慢指针走一步
        fast_pointer = fast_pointer->next->next;  // 快指针走两步
    }

    if (slow_pointer == fast_pointer)
        return slow_pointer;

    return nullptr;
}

2.7 在一个有环链表中找到环的入口

参考 2.6 图,若存在环且找到了相遇点 C,此时令一个指针 start_node 从链表第一个结点处开始往后遍历,再令另一个指针 meet_node 从 C 处往后遍历,它们的相遇结点就是环的入口点。为什么呢?

2.6 公式已经证明了:若快慢指针相遇在 C 点,则:

$$ AB+BC=nr \tag{其中 $n=n_1-2n_2$} $$

进一步整理上式为:

$$ AB=(r-BC)+(n-1)r \tag{其中 r-BC 的含义请对照 2.6 图} $$

好了,至此,证明就已经很显然了。当 start_node 走了 r-BC 距离后,meet_node 正好到达入口处 B 点,此时 start_node 还剩 (n-1)r 距离,显然两个指针继续走的话,一定会相遇在入口处 B 点。

/* 在一个有环链表中找到环的入口 */
Node * find_meet_node(Node * header)
{
    Node * meet_node = is_loop(header);
  
    if (meet_node == nullptr)  // 不存在环
        return nullptr;
  
    Node * start_node = header->next;
    while (start_node != meet_node)
    {
        start_node = start_node->next;
        meet_node = meet_node->next;
    }
  
    return start_node;
}

此外,我们也会遇到 "判断两个链表是否相交","求出两个相交链表的交点" 这样的问题,百变不离其宗,我们只需把链表尾接到其中一个链表头就转化为 2.6 和 2.7 的问题,所以在这里不作详述了。

2.8 删除当前结点

题意规定,给定要删除的结点和头结点,现要你删除这个结点,要求平均时间复杂度为 $T(n)=O(1)$。

例如,现有这样的链表,1->2->3->4->5->6,需要删除 4,我们的思路肯定是先找到 4 的前一个结点 3 和后一个结点 5,然后把 3 和 5 连起来,再把 4 删除。但是这样做的话,我们需要花费 $O(n)$ 的时间来找到 3 和 5,与题意要求的 $O(1)$ 相距甚远。

我们之所以需要从头结点开始查找要删除的结点,是因为我们需要得到要删除结点的前一个结点。我们试着换一种思路。如果我们要删除 4,可以把 4 和 5 的数据交换下,然后删除 5,再把 4 和 6 连接起来,如此其时间复杂度为 $O(1)$。

上面的思路还有一个问题:如果删除的结点位于链表的尾部,没有下一个结点,怎么办?我们仍然从链表的头结点开始,顺便遍历得到给定结点的前序结点,并完成删除操作。这个时候时间复杂度是 $O(n)$。那题目要求我们需要在 $O(1)$ 时间完成删除操作,我们的算法是不是不符合要求?实际上,假设链表总共有 n 个结点,我们的算法在 n-1 种情况下,时间复杂度是 $O(1)$,只有当给定的结点处于链表末尾的时候,时间复杂度为 $O(n)$。因此其平均时间复杂度 $\frac {(n-1)⋅O(1)+1⋅O(n)}n$,仍然为 $O(1)$。

/* 删除当前结点 */
void del(Node * header, Node * position)
{
    if (!position->next)  // 要删除的是最后一个结点
    {
        Node * p = header;
        while (p->next != position)
            p = p->next;  // 找到 position 的前一个结点
        p->next = nullptr;
        delete position;
    }
    else
    {
        Node * p = position->next;
        swap(p->data, position->data);
        position->next = p->next;
        delete p;
    }
}

2.9 找出单链表的中间结点

题意要求,给定链表头结点,在最小复杂度下输出该链表的中间结点。

如果只知链表的头结点,我们一般的思路就是先遍历链表得到链表长度,然后再遍历一遍得到中间结点,如此时间复杂度为 $O(n)+O(\frac n2)$。

上面的思路似乎不太令人满意。我们又想到快慢指针,它有一个很重要的性质:慢指针走的长度等于快慢指针相距的程度。所以利用这个性质,当快指针走到链表尾时,慢指针正好在中间结点。

/* 找出单链表的中间结点 */
Node * find_middle(Node * header)
{
    Node * slow_pointer = header;
    Node * fast_pointer = header;

    while (fast_pointer->next && fast_pointer->next->next)
    {
        slow_pointer = slow_pointer->next;        // 慢指针走一步
        fast_pointer = fast_pointer->next->next;  // 快指针走两步
    }

    return slow_pointer;
}

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-08-02
原文链接:https://ethsonliu.com/2019/08/single-linked-list-interview.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。