单链表的题目整理

2018-08-16

这两天复习了下线性表的相关题目，在这里针对错题做一个简单的整理。

关于链表，有以下几种经典的题型：

针对经典题型，应当记下经典的算法，以便应用。另又将教材及《剑指Offer》中的例题整理如下。（对于基本的定义、插入、删除、查找操作就不在此总结了）

单链表排序

题目：

有一个带头结点的单链表L，设计一个算法使其元素递增有序。

算法思想：

采用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然后依次扫描单链表中剩下的结点$current$（直至current == NULL为止），在有序表中通过比较查找插入$current$ 的前驱结点$p$，然后将 $current$ 插入 $*p$ 之后。

void sort(LNode *head) {
    LNode* current = head->next;
    head->next = NULL;
    while (current != NULL) {
        LNode* p = head;
        while (p->next != NULL && p->next->data < current->data) {
            p = p->next;
        }
        LNode* r = current->next; //保存下一个结点
        current->next = p->next;
        p->next = current;
        current = r;
    }
}

该算法的时间复杂度为$O(n^2)$，也可以采取空间换时间的策略，先将链表的数据复制到数组中并排序，如此时间复杂度为$O(log_2n)$。

单链表的公共结点

题目：

给定两个单链表，编写算法找出两个链表的公共结点

（该题目在【2012年计算机联考】中出现过）

算法思想：

我们知道，对于单链表中的每个结点来说，next指针指向唯一一个结点，因此两个单链表从第一个公共结点开始，后续结点均相同。是以，两个有公共结点而部分重合的链表，拓扑形状看起来像Y，而不可能像X。

容易想到一种暴力求解方法：在第一个链表中遍历每一个结点，每遍历一个结点，又对另一个链表的结点从头到尾进行遍历，如果找到两个相同的结点，就找到了两个单链表的公共结点，时间复杂度为$O(len1 * len2)$

我们可不可以在更短的时间内完成公共结点的查找？我们注意到这样一个事实，如果两个单链表存在公共结点，那么从第一个公共结点开始到尾结点全部重合，因此判断两个单链表是否有重合的部分，只需分别遍历两个链表到最后一个结点，如果两个结点是一样的，则说明他们有公共结点，否则不存在公共结点。

那又要如何得到第一个公共结点？如果两个单链表有重合部分，那么从第一个公共结点到最后一个结点的长度是相同的。假设一个链表比另一个链表长k个结点，那么第一个公共结点不可能存在较长链表中刚开始的k个结点中（如果存在，则第一个公共结点开始到尾结点的长度则不同）。我们先在长的链表中遍历k个结点，之后两个链表再同步遍历，此时就能同时到达第一个公共节点了（如果存在的话）。

具体步骤如下：

分别遍历两个链表，得到他们的长度，并求出两个长度之差k
长的链表先遍历k个结点
两个链表同步遍历
第一个相同的结点为第一个公共结点
如果直到链表结束都没有碰到相同的结点，则说明两个链表没有重合部分

时间复杂度为$O(len1 + len2)$

struct Node {
    char data;
    Node* next;
};
/*求链表的长度*/
int listlen(Node * head) {
    int len = 0;
    Node* p = head;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}
Node* findNode(Node* l1, Node* l2) {
    int m = listlen(l1);
    int n = listlen(l2);
    Node* p = l1->next;
    Node* q = l2->next;
    if (m > n) {
        for (int i = n; i <= m; i++) p = p->next;
    } else if (m < n) {
        for (int i = m; i <= n; i++) q = q->next;
    }
    while (p != NULL && q != NULL) {
        if (p == q) return p;
        p = p->next;
        q = q->next;
    }
    return NULL;
}

单链表中倒数k个结点

题目：

输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个节点。例如，一个链表有6个结点，从头结点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第三个结点是值为4的结点。

（该题目摘自《剑指Offer》，在【2009年计算机联考】中亦出现过）

算法思想：

由于单链表只能往后走而不能往前走，因此我们不能走到链表的末端再往前回溯k个结点。如果我们先遍历链表得到链表的长度 n，再计算出单链表中倒数 k 个结点为正数（n - k + 1）个结点，未免有些麻烦。

我们换一种思路。假设有两个指针 p 和 q，两个指针相距（k - 1）个结点，p 指针在后，q 指针在前。两个指针同步往后遍历。当 p 指针到达链表的末尾时，q 指针刚好指向倒数第k个结点。

struct Node {
    int data;
    Node* next;
};
Node* searchK(Node* head, int k) {
    if (head == NULL || k == 0) return NULL;
    Node* p = head->next;
    Node* q = head->next;
    for (int i = 0; i < k - 1; i++) {
        p = p->next;
        if (p == NULL) return NULL;   //链表长度小于k
    }
    while (p->next != NULL) {
        p = p->next;
        q = q->next;
    }
    return q;
}