2.3.7

t2.3.7

q1

设计一个递归算法,删除不带头结点的单链表 $L$ 中所有值为 $x$ 的结点。

void recursionByVal(LinkList &L, ElemType value) {
    if (L == NULL)
        return;
    if (L->data == value) {
        // 删除当前结点
        Node *p = L;
        L = L->next;
        free(p);
        recursionByVal(L, value);
    } else {
        recursionByVal(L->next, value);
    }
}

提示

需要注意的是在判断时两个分支中递归的传参，一个是L，一个是L->next,前面传参L是因为已经在本轮递归中有L=L->next的操作

// 另外一种解法
void DelRes(LinkList &p, ElemType x){
    if(p->next == NULL) return; //递归终止
    if(p->next->data == x){ //只需要判断当前结点的下一个值是否为x
        LinkList q = p->next;
        p->next = p->next->next;
        free(q);
    } 
    DelRes(p->next, x);// 每次递归传的这个p->next的data是已经处理过的了
}
// 多写一个函数并在另外一个函数里边开始调用，封装性更好
void IgnoreHead(LinkList &L, ElemType x){
    DelRes(L,x);
    // 单独处理第一个
    if(L!=NULL&&L->data == x){
        LinkList p = L;
        L = L->next;
        free(p);
    }
}

提示

每次递归这个p->next的data是已经处理过的了，这就有一个问题，第一个结点没有处理，所以在重新写一个函数里边单独处理，而不在main函数里边写封装性更好

q2

在带头结点的单链表 $L$ 中,删除所有值为 $x$ 的结,点,并释放其空间,假设值为 $x$ 的结点不唯一,试编写算法以实现上述操作。

在这里借鉴第一题我们给出两种解法，一个是按常规正向顺序操作，另一个表示递归操作

/**
 * 直接顺序遍历，进行删除
 * @param L
 * @param data
 */
void delEleByVal(LinkList &L, ElemType data) {
    Node *p = L;
    while (p != NULL && p->next != NULL) {
        if (p->next->data == data) {
            // 删除结点
            Node *tmp = p->next;
            p->next = tmp->next;
            free(tmp);
        }
        p = p->next;
    }
}

注意

这里需要注意while循环条件，尽管条件中存在p->next != NULL,那么p就真的不会移动到NULL的位置吗？-- 若最后一个元素是要删除的元素，则在p->next = tmp->next这一步，会导致p->next为NULL，进而导致下一轮循环时p值为NULL

/**
 * 递归删除
 */
void delEleRecursion(LinkList &L, ElemType data) {
    // 递归终止条件
    if (L->next == NULL)
        return;
    if (L->next->data == data) {
        // 删除
        Node *p = L->next;
        L->next = p->next;
        free(p);
        delEleRecursion(L, data);
    } else {
        delEleRecursion(L->next, data);
    }
}

// 另外一种解法和第一题一样，还不用单独处理第一个结点
void DelRes(LinkList &p, ElemType x){
    if(p->next == NULL) return; //递归终止
    if(p->next->data == x){ //只需要判断当前结点的下一个值是否为x
        LinkList q = p->next;
        p->next = p->next->next;
        free(q);
    } 
    DelRes(p->next, x);// 每次递归传的这个p->next的data是已经处理过的了
}

q3

设 $L$ 为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值

/**
 * 逆序输出链表
 * @param L
 */
ListReverse(LinkList &L) {
    if (L->next != NULL) {
        ListReverseShow(L->next);
    }
    cout << L->data << " ";
}

void ListReverseShow(LinkList &List) {
	if (List -> next) ListReverseShow(List->next);
}

提示

在调用递归函数之前，需要排除掉头结点的影响，此外本题也可用栈来解决

注意

若对递归函数需要进行一些预处理，应当放到另一个函数中处理，然后调用对应的递归函数，考试时是不会让你写main函数的

q4

试编写在带头结点的单链表 $L$ 中删除一个最小值结点的高效算法(假设最小值结点是唯一的)

/**
 * 删除最小值的结点(默认只有一个最小值)
 * 思路就是遍历一遍，保存最小值结点的前驱
 * @param L
 */
void delMinEle(LinkList &L) {
    Node *prev = L, *p = L->next, *mNode = L->next, *mNodePrev = L;
    while (p != NULL) {
        if (p->data < mNode->data) {
            mNodePrev = prev;
            mNode = p;
        }
        prev = p;
        p = p->next;
    }
    // 将最小值结点删除
    mNodePrev->next = mNode->next;
    free(mNode);
}

void DelMin(LinkList &L){
    if(L->next == NULL) return;
    else{
        LinkList p = L->next, q = L; //q用来记录当前最小结点的上一个结点
        ElemType min = p->data;
        while(p->next != NULL){
            if(p->next->data < min){
                min = p->next->data;
                q = p;
            }
            p = p->next;
        }
        // 循环结束后q就是最小结点的上一个结点
        LinkList temp = q->next;
        q->next = q->next->next;
        free(temp);
    }
}

提示

需要有四个指针变量
fang：不需要四个指针，只需要一个当前的工作指针和最小值的前一个指针就行，int形变量保存最小值

q5

试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为 $O(1)$ 。

/**
 * 带头结点的单链表就地逆置
 * 将头结点摘下，遍历后续结点用头插法插入
 * @param L
 */
void ListReverse(LinkList &L) {
    Node *p = L->next, *tmp;
    L->next = NULL;
    while (p != NULL) {
        tmp = p;
        p = p->next;
        tmp->next = L->next;
        L->next = tmp;
    }
}

q6

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

/**
 * 以下是王道上的标准答案，更简洁
 * @param L
 */
void sort(LinkList &L) {
    Node *p = L->next, *pre;
    Node *r = p->next; // r保持*p后继结点指针，以保证不断链
    p->next = NULL; // 构造只含一个数据结点的有序表
    p = r;
    while (p != NULL) {
        r = p->next; // 保存*p的后继结点指针
        pre = L;
        while (pre->next != NULL && pre->next->data < p->data)
            pre = pre->next;
        p->next = pre->next;
        pre->next = p;
        p = r; // 扫描原单链表中剩下的结点
    }
}

/**
 * 使单链表递增有序
 * @param L
 */
void toInc(LinkList &L) {
    // 遍历原链表的指针
    Node *move = L->next, *move_prev = L;
    L->next = NULL; // 专门取出头结点
    while (move != NULL) {
        // 遍历排序后链表的指针
        Node *p = L->next, *p_prev = L;
        while (p != NULL) {
            if (p->data > move->data) {
                // 此时将move的值插入到p指向结点的前面
                move_prev = move;
                move = move->next;
                p_prev->next = move_prev;
                move_prev->next = p;
                break; // 退出循环
            }
            p_prev = p;
            p = p->next;
        }
        // 此时将结点添加到末尾
        if (p == NULL) {
            move_prev = move;
            move = move->next;
            p_prev->next = move_prev;
            move_prev->next = NULL;
        }
    }
}

提示

一个是自己写的，大概思路和王道的差不多，设置了四个指针变量，主要是分为两层循环，一层循环是遍历原链表，另一层是遍历排序后的链表，进行比较，将原链表中的元素插入到排序后的链表的指定位置
王道的那个还没仔细看，后续再完善

q7

设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素的元素（若存在）。

 void DelBet(LinkList &L,ElemType min, ElemType max){
    Node *p = L->next;
    Node *pre = L;
    while(p != NULL){
        if(p->data > min && p->data < max){
            Node *temp = p;
            p = p->next;
            pre->next = p;
            free(temp);
        }
        else{
            pre = p;
            p = p->next;
        }
    }
}

 void DelBet(LinkList &L,ElemType min, ElemType max){
    Node *p = L->next;
    Node *pre = L;
    while(p != NULL){
        if(p->data > min && p->data < max){
            Node *temp = p;
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
        else{
            pre = p;
            p = p->next;
        }
    }
}

提示

王道：先free(q)，q的值不变只是q指向的内存值可能会变，所以先free再赋值没有问题^[1]
fang: 一定要记得给p赋值，往后遍历

q8

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

提示

若链表存在公共结点，则表明两个链表是一个"Y"型结构，具体思路可以是：

先分别遍历两个链表，求出各自长度
计算长度差 $k$ ,让长的链表先遍历 $k$ 位
再同步遍历两个链表，直到找到公共结点或者一直到链表结束

q13

典型假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。

void ListMerge(LinkList &L1, LinkList &L2) {
    Node *r, *p1 = L1->next, *p2 = L2->next;
    L1->next = NULL; // L1作为结果链表的头指针，先初始化为空
    while (p1 && p2)
        if (p1->data < p2->data) {
            // 较小结点头插法插入
            r = p1->next; // 暂存，防止断链
            p1->next = L1->next;
            L1->next = p1;
            p1 = r;
        } else {
            r = p2->next;
            p2->next = L1->next;
            L1->next = p2;
            p2 = r;
        }
    if (p1) 
        p2 = p1; // 通常，p1，p2此时有一个非空
    while (p2) {
        r = p2->next;
        p2->next = L1->next;
        L1->next = p2;
        p2 = r;
    }
    free(L2);
}

相关信息

表 $A,B$ 都有序,可从第一个元素起依次比较 $A,B$ 两表的元素,若元素值不等, 则值小的指针往后移,若元素值相等,则创建一个值等于两结点的元素值的新结点,使用尾插法插入到新的链表中,并将两个原表指针后移一位,直到其中一个链表遍历到表尾。
本题是一道非常典型的题目，相关算法应该熟练掌握

q14

设 $A$ 和 $B$ 是两个单链表(带头结点),其中元素递增有序。设计一个算法从 $A$ 和 $B$ 中的公共元素产生单链表 $C$ ,要求不破坏 $A,B$ 的结点。

void ListCommon(LinkList &La, LinkList &Lb, LinkList &Lc) {
    Node *r, *pa = La->next, *pb = Lb->next, *pc = Lc;
    while (pa && pb) {
        if (pa->data == pb->data) {
            // 创建结点插入到pc中
            r = (Node *) malloc(sizeof(Node));
            r->data = pa->data;
            r->next = NULL; // 也可以放在循环结束后
            pc->next = r;
            pc = r; // pc为链表C的尾指针，方便后续尾插法插入结点
            pa = pa->next;
            pb = pb->next;
        } else if (pa->data < pb->data) {
            pa = pa->next;  // pa后移
        } else {
            pb = pb->next; // pb后移
        }
    }
    // 此时pa,pb可能只有一个为NULL，但剩下的肯定没有公共元素
}

相关信息

表 $A,B$ 都有序,可从第一个元素起依次比较 $A,B$ 两表的元素,若元素值不等, 则值小的指针往后移,若元素值相等,则创建一个值等于两结点的元素值的新结点,使用尾插法插入到新的链表中,并将两个原表指针后移一位,直到其中一个链表遍历到表尾。
等于是把两个链表当做一个链表进行“遍历”

注意

若 A 和 B 中存在重复元素，产生的链表 C 中也不会有,题目中说的是公共元素，那么这个就不会重复

q15

已知两个链表A和B分別表示两个集合,其元素递增排列。编制函数求A与B的交集,并存放于A链表中。

LinkList ListIntersection(LinkList &La, LinkList &Lb) {
    Node *pa = La->next, *pb = Lb->next;
    Node *u, *pc = La;
    while (pa && pb) {
        if (pa->data == pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            u = pb;
            pb = pb->next;
            free(u);
        } else if (pa->data < pb->data) {
            u = pa;
            pa = pa->next;
            free(u);
        } else {
            u = pb;
            pb = pb->next;
            free(u);
        }
    }
    // 运行到此处，pa或pb至少有一个为 NULL
    // 若pa不为NULL，则pb为NULL
    //令 pb=pa，便于后续统一处理
    if (pa) pb = pa;
    while (pb) {
        u = pb;
        pb = pb->next;
        free(u);
    }
    pc->next = NULL; // pc为尾指针
    free(Lb);
    return La; // 不返回也是可以的，因为函数参数为引用
}

相关信息

算法思想和14题类似，但也有不同，本题需要将交集放到链表 $A$ 中，同时要求将其他结点进行释放
采用归并的思想,设置两个工作指针 pa 和pb,对两个链表进行归并扫描,只有同时出现在两集合中的元素才链接到结果表中且仅保留一个,其他的结点全部释放。当一个链表遍历完毕后,释放另一个表中剩下的全部结点。
此外需要注意的时，标准写法中是如何删除一个结点的链表中的临时指针变量

q16

两个整数序列 $A=a_{1},a_{2},a_{3}\dots,a_{m}$ 和 $B=b_{1},b_{2},b_{3},\dots,b_{n}$ 已经存入两个单链表中,设计一个算法,判断序列 $B$ 是否是序列 $A$ 的连续子序列

提示

因为两个整数序列已存入两个链表中,操作从两个链表的第一个结点开始,若对应数据相等,则后移指针:若对应数据不等,则A链表从上次开始比较结点的后继开始,B链表仍从第一个结点开始比较,直到B链表到尾表示匹配成功。A链表到尾而 B链表未到尾表示失败。操作中应记住 A链表每次的开始结点,以便下次匹配时好从其后继开始。

q17

设计一个算法用于判断带头结点的循环双链表是否对称

q18

有两个循环单链表,链表头指针分別为 $h_{1}$ 和 $h_{2}$ ,编写一个函数将链表 $h_{2}$ 链接到链表 $h_{1}$ 之后,要求链接后的链表仍保持循环链表形式。

q19

设有一个带头结点的循环单链表,其结点值均为正整数。设计一个算法,反复找出;单链表中结点值最小的结点并输出,然后将该结点从中删除,直到单链表空为止,再删除表头结点。

q20

设头指针为 $L$ 的带有表头结点的非循环双向链表,其每个结点中除有pre(前驱指针)、data(数据)和next(后继指针)域外,还有一个访问频度域freq。在链表被启用前,其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时,令元素值为 $x$ 的结,点中freq 域的值增 1,并使此链表中结,点保持按访问频度非增(递减)的顺序排列,同时最近访问的结点排在频度相同的结点前面,以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。

LinkList Locate(LinkList &L, ElemType x) {
    Node *p = L->next, *q;
    // 查找值为 x 对应的结点
    while (p && p->data != x)
        p = p->next;
    if (!p)
        exit(0); // 不存在
    else {
        p->freq++; // 访问频度+1
        if (p->pre == L || p->pre->freq > p->freq)
            return p; // p本身已经在表首或已经在该在的位置
        if (p->next != NULL) p->next->pre - p->pre;
        p->pre->next = p->next; // 摘下 p结点
        q = p->pre;
        // 寻找p结点的插入位置
        while (q != L && q->freq <= p->freq) // <= 条件会将结点排在同频率的第一个
            q = q->pre;
        p->next = q->next;
        if (q->next != NULL)
            q->next->pre = p;
        p->pre = q;
        q->next = p;
    }
    return p;
}

提示

首先在双向链表中查找数据值为 $x$ 的结点,查到后,将结点从链表上摘下,然后顺着结点的前驱链查找该结点的插入位置(频度递减,且排在同频度的第一个,即向前找到第一个比它的频度大的结点,插入位置为该结点之后),并插入到该位置。

q21

典型单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是空的)。试编写算法判断单链表是否存在环。
1)给出算法的基本设计思想。
2)根据设计思想,来用C或Java语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。

Node *FindLoopStart(LinkList &L) {
    Node *fast = L, *slow = L;
    // fast 一次移动两个结点距离
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (fast == NULL || fast->next == NULL)
        return NULL; // 没有环
    Node *p1 = L, *p2 = slow; // 分别指向开始点、相遇点
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

int main() {
    LinkList List;
    InitList(List);
    ListInsert(List, 1);
    ListInsert(List, 2);
    Node *p1 = ListInsert(List, 3);
    ListInsert(List, 4);
    ListInsert(List, 5);
    ListInsert(List, 6);
    ListInsert(List, 7);
    ListInsert(List, 8);
    Node *p2 = ListInsert(List, 9);
    ListShow(List); // 展示原始链表
    p2->next = p1; // 将尾结点next域指向结点 3
    Node *start = FindLoopStart(List);
    cout << start->data << endl;
    return 0;
}

1 2 3 4 5 6 7 8 9 
3

相关信息

设置快慢两个指针分别为 fast 和 slow,初始时都指向链表头head。 slow 每次走一步, 即 slow=slow->next; fast每次走两步,即fast=fast->next->next。由于 fast 比slow 走得快,如果有环,那么 fast 一定会先进入环,而 slow 后进入环。当两个指针都进入环后, 经过若干操作后两个指针定能在环上相遇。这样就可以判断一个链表是否有环。
由于 fast移动速度是slow的两倍，故我们可以得到如下的等式（相同时间内，fast指针移动的距离是slow指针的两倍）：

2(a+x) = a+nr+x

得

a+x=nr

由上述得到的关系式，可知 $a+x$ 的距离等于fast指针走 $n$ 圈的距离，我们可以设置两个指针一个指向head，一个指向相遇点，以同等的速度移动，当恰好相遇时，就是环的入口

疑问解答

如何确保slow指针还未走完一圈，fast指针就已追上？

我们可以假设slow速度为 $v$ ，则fast指针速度为 $2v$ ,当slow进入环时，fast已在环内，此时最坏的情况是，fast指针恰好在slow紧邻的前面，这样两指针相遇，需要fast指针多走一圈^[2]，假设slow走一圈所需时间为 $T$ ，则有 $T=r/v$ ,若fast追上则需多走一圈,所需时间为 $r/(2v-v)=r/v$ ，因此，fast可以在slow走完一圈前追上slow

环的入口是原本链表的尾结点吗？

显然这里的入口点并不是之前链表的尾结点，而是原本链表尾结点指针指向的那个结点，虽然严格意义上来说，只有指针移动到原来的尾结点，才会进入"循环"^[3]，但事实上，从这个入口，确实已经进入到了环

q22

统考真题已知一个带有表头结点的单链表,假设该链表只给出了头指针 list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第 $k$ 个位置上的结点( $k$ 为正整数)。若查找成功,算法揄出该结点的data域的值,并返回1;否则,只返回0。

提示

设置两个指针， $p$ 和 $q$ ，当 $p$ 移动到第 $k$ 个结点时， $q$ 开始移动，则 $p$ 移动到表尾时， $q$ 正好是倒数第 $k$ 个位置

q23

假定采用带头结点的单链表保存单词,当两个单词有相同的后级时, 可共享相同的后缀存储空问;例如loading 和being 的存储映像如下图所示。

设str1 和str2分別指向两个单词所在单链表的头结点,,请设计一个时间上尽可能高效的算法,找出由str1 和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置 $p$ )。

提示

和第八题神似

q24

统考真题用单链表保存m个整数,且 $|data|\le n$ ( $n$ 为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data 的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表 head 如下

相关信息

算法的核心思想是用空间换时间。使用辅助数组记录链表中己出现的数值,从而只需对链表进行一趟扫描。
因为 $|data|\le n$ ,故辅助数组 $q$ 的大小为 $n+1$ ,各元素的初值均为 $0$ 。依次扫描链表中的各结点,同时检查 $q[|data|]$ 的值,若为 $0$ 则保留该结点,并令 $q[|data|]=1$ :否则将该结点从链表中删除。
时间复杂为为 $O(m)$ ，空间复杂度为 $O(n)$

q25

设线性表 $L=(a_{1},a_{2},a_{3},\dots,a_{n-2},a_{n-1},a_{n})$ 来用带头结点的单链表保存,请设计一个空间复杂度为 $O(1)$ 且时间上尽可能高效的算法,重新排列 $L$ 中的各结点,得到线性表

L^{'}=(a_{1},a_{n},a_{2},a_{n-1},a_{3},a_{n-2},\dots)

提示

发现 $L^{'}$ 是由 $L$ 摘取第一个元素,再摘取倒数第一个元素...依次合并而成的。为了方便链表后半段取元素,需要先将 $L$ 后半段原地逆置^[4]。

先找出链表工的中间结点,为此设置两个指针 $p$ 和 $q$ ,指针 $p$ 每次走一步,指针 $q$ 每次走两步,当指针 $q$ 到达链尾时,指针 $p$ 正好在链表的中间结点
然后将 $L$ 的后半段结点原地逆置^[5]。
从单链表前后两段中依次各取一个结点,按要求重排。

时间复杂度为 $O(n)$

就不存在q已经不在的说法 ↩︎
事实上，只是将近一圈，我们假设环上结点数为 $m$ ，则两者相遇，需要fast多走 $m-1$ 个结点 ↩︎
在这之前，和普通的链表遍历并无区别 ↩︎
题目要求空间复杂度为 $O(1)$ ,不能借助栈了,否则每取最后一个结点都需要遍历一次链表 ↩︎
参考q5 ↩︎

2.3.7

# 2.3.7

# t2.3.7

# q1

# q2

# q3

# q4

# q5

# q6

# q7

# q8

# q13

# q14

# q15

# q16

# q17

# q18

# q19

# q20

# q21

# q22

# q23

# q24

# q25

2.3.7

t2.3.7

q1

q2

q3

q4

q5

q6

q7

q8

q13

q14

q15

q16

q17

q18

q19

q20

q21

q22

q23

q24

q25