数据结构｜有关链表的练习题

链表定义

typedef struct LNode{
    int data;
    LNode* next;
}LNode, *LinkList;

有关链表的一些基础函数

typedef struct LNode{
    int data;
    LNode* next;
}LNode, *LinkList;

// 循环双链表
typedef struct DNode{
    int data;
    DNode* prior;
    DNode* next;
}DNode, *DLinkList;

void Init(LinkList &L){
    L = (LinkList)malloc(sizeof(LNode));
    LNode* p;
    LNode *r = L;
    for(int i = 0; i < 8; i++){
        p = (LNode*)malloc(sizeof(LNode));
        if(i <= 3)
            p->data = i;
        else
            p->data = 8-1-i;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}


void PrintList(LinkList L){
    LNode* p = L->next;
    while(p != NULL){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

// 利用头插法逆置
void Reverse(LinkList& L){
    LNode* p = L->next;
    L->next = NULL;
    LNode* r = L;
    while(p != NULL){
        r = p->next;  // 暂存p的下一个指针
        L->next = p;
        p->next = L->next;
        p= r;
    }
}

// 法2 设置3个指针逆置
Linklist reserve(LinkList L)
{
　　LNode *pre,*p=L->next,*r=p->next;
　　p->next=NULL;//处理第一个结点
　　while(r!=NULL)//r为空，则说明p为最后一个结点

　　{
　　　　pre=p;//依次遍历
　　　　p=r;
　　　　r=r->next;
　　　　p->next=pre;//指针反转
　　}
　　L->next=p;//处理最后一个结点
　　return L;
}

int Length(LinkList L){
    LNode *p = L->next;
    int res = 0;
    while(p != NULL){
        res++;
        p = p->next;
    }
    return res;
}

给定两个单链表，找出两个链表的公共结点。
如果有公共结点，则两个链表一定是Y形重合，而不是X，因为每个结点都只有一个next域，所以只要最后一个结点重合，那么这两个链表就有公共结点。但是两个链表的长度不一定一样，所以遍历的时候做不到同步，假设长链表比短链表多k个元素，那么就可以先遍历长链表k步，然后再一起遍历，做到同步。

LinkList FindCommon(LinkList L1, LinkList L2){
    int len1 = Length(L1);
    int len2 = Length(L2);
    int dist = 0;
    LinkList longlist, shortlist;
    if(len1 > len2){
        dist = len1-len2;
        longlist = L1->next;
        shortlist = L2->next;
    }
    else{
        dist = len2 - len1;
        longlist = L2->next;
        shortlist = L1->next;
    }
    while(dist--){
        longlist = longlist->next;
    }
    while(longlist != NULL){
        if(longlist == shortlist)
            return longlist;
        else{
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
    }
    return NULL;
}

有一个带头结点的单链表L，给其排序使元素递增
插入排序的思想，首先构建只有一个结点的链表，然后遍历剩下的元素，插入排序。

LNode* Sort(LinkList& L){
    LNode* p = L->next;
    LNode* pre;
    LNode* r = p->next;
    p->next = NULL;  // 只有第一个结点
    p = r;  // 从p的下一个结点开始遍历
    while(p != NULL){
        r = p->next;  // 保存p的后继，避免之后被覆盖，因为p还要迭代
        pre = L;  // pre代表已排好序的链表，从一开始找到p插入的位置
        while(pre->next != NULL && pre->next->data < p->data){
            pre = pre->next;
        }
        p->next = pre->next;  // pre作为前驱，将p放在pre后面
        pre->next = p;
        p = r;  // 迭代
    }
    return L->next;
}

给定链表，x值，y值，删掉链表当中介于x和y之间的结点

void Del_xy(LinkList& L, int x, int y){
    LNode *p = L->next;
    LNode *pre = L;
    LNode* q;
    while(p != NULL){
        if(p->data > x && p->data < y){
            q = p;
            pre->next = p->next;
            free(q);
        }
        pre = pre->next;
        p = p->next;
    }
}

给定带头结点的单链表，head为头指针，按递增次序输出单链表中各结点的数值，并释放结点所占空间（不允许用数组作为辅助空间）。
法1: 先对链表排序，然后输出
法2: 每次遍历找到最小值，然后输出并释放，直到链表为空。

void Min_Del(LinkList &head){
    LNode *p = head->next;
    while(head->next != NULL){
        // 接下来这三步初始化很重要
        LNode *min_pre = head; // 最小元素的前驱
        int minn = head->next->data;  // 记录最小元素
        p = head->next;  // 每次从头开始遍历
        while(p->next != NULL){
            if(p->next->data < minn){
                minn = p->next->data;
                min_pre = p;  // 最小元素的前驱
            }
            p = p->next;
        }
        LNode *min_p = min_pre->next;
        min_pre->next = min_p->next;
        cout<<min_p->data<<" ";
        free(min_p);
    }
    cout<<endl;
    free(head);  // 释放掉头结点
}

将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A中含有原表中序号为奇数的元素，B中含有原表中序号为偶数的元素，且相对顺序不变。
把A置空，给B分配空间，分别利用尾插法构建链表。最后一定要记着将尾结点的next置空。

void Seperate(LinkList& A, LinkList& B){
    B = (LinkList)malloc(sizeof(LNode));  // 分配空间
    B->next = NULL;  // 尾结点置空
    int i = 0;  // 用于计数
    LNode* p = A->next;  // 存储A的下一个元素
    A->next = NULL;  // A表尾结点置空
    LNode* q = B;  // q作为B的尾结点
    LNode* ra = A;  // ra作为A的尾结点
    while(p != NULL){
        if(i % 2 == 0){
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            new_node ->next = NULL;
            q->next = new_node;
            q = new_node;  // 更新尾指针
        }
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            new_node ->next = NULL;
            ra->next = new_node;
            ra = new_node;
        }
        p = p->next;
        i++;
    }
    ra->next = NULL;  // 最后的尾结点置空
    q->next = NULL;
}

A和B是两个递增的单链表，用他们的公共元素产生单链表C，不破坏A，B中的元素。

LinkList Union_Merge(LinkList L1, LinkList L2){
    LNode *p =L1->next;
    LNode *q = L2->next;
    LinkList C;
    C = (LinkList)malloc(sizeof(LNode));
    C->next = NULL;
    LNode* r = C;  // 记录C的尾指针
    while(p != NULL && q != NULL){
        if(p->data < q->data)
            p = p->next;
        else if(p->data > q->data)
            q = q->next;
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            r->next = new_node;
            r = new_node;
            p = p->next;
            q = q->next;
        }
    }
    r->next = NULL;
    return C;
}

A,B是两个递增的单链表，求A与B的公共元素集合，并放入A链表中

void Find_Common(LinkList A, LinkList B){
    LNode *p = A->next;
    LNode *ra = A;  // 用来构建新的A表
    A->next = NULL;
    LNode *q = B->next;
    while(p != NULL && q != NULL){
        if(p->data < q->data)
            p = p->next;
        else if(p->data > q->data)
            q = q->next;
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            ra->next = new_node;
            ra = new_node;
            p= p->next;
            q = q->next;
        }
    }
    ra->next = NULL;
}

对于链表中data的绝对值相等的结点，仅保留第一次出现的结点，而删除其余绝对值相等的结点。
用一个辅助数组记录

void Del_abs(LinkList L, int n){
    int array[n+1];  // 辅助数组
    memset(array, 0,sizeof(array));  // 初始化数组
    LNode *p = L->next;
    LNode *pre = L;  // 作为p的前驱
    while(p != NULL){
        int num = abs(p->data);
        if(array[num] == 0)
            array[num]= 1;
        else{  // 如果之前出现过，则删除该结点
            pre->next = p->next;
            LNode *q = p;
            free(q);
        }
        p = p->next;  // 移动指针
        pre = pre->next;
    }
}

有两个循环单链表，编写函数使得h2链接到h1之后，要求链接后的链表仍保持循环链表形式

typedef struct CNode{
    int data;
    CNode* next;
}CNode, *CList;

CList Joint(CList C1, CList C2){
    CNode *p = C1;  // 指向C1，C2的尾指针
    CNode *q = C2;
    while(p->next != C1){
        p = p->next;
    }
    
    while(q->next != C2){
        q = q->next;
    }
    p->next = C2;  //连接
    q->next = C1;  // 循环
    return C1;
}

判断序列B是否是序列A的字序列
设置两个工作指针p，q，用pre记录每次A中开始比较的结点，如果数据相等，向后移动指针，如果数据不相等，pre后移，即从一个新的结点开始匹配，q返回到B的第一个结点，这里默认链表不带头结点。

int IsSub(LinkList &A, LinkList &B){
    LNode *p = A;
    LNode *pre = p;  // 记录每次开始比较的结点
    LNode *q = B;
    while(p && q){
        if(p->data == q->data){
            p = p->next;
            q = q->next;
        }
        else{
            pre = pre->next;  // 没有匹配成功，从一个新的结点开始比较
            p = pre;
            q = B;
        }
    }
    if(q == NULL)  // 代表B已经匹配完
        return 1;
    else
        return 0;
}

删掉有序链表中的相同元素

void Del_dup(LinkList &L){
    LNode *pre = L->next;
    if(pre == NULL)
        return;
    LNode *p = pre->next;
    while(p != NULL){
        if(pre->data == p->data){
            LNode *q = p;
            p = p->next;
            pre->next = p;
            free(q);
        }
        else{
//   这部分一定要放到else当中，删掉相同结点的话 pre不变，p后移
            pre = pre->next;
            p = p->next;
        }
    }
}

设 $C=\{a_1,b_1,a_2,b_2......a_n,b_n\}$ 为线性表，将其拆分为两个链表，其中 $C1=\{a_1,a_2,......a_n \} ，C2=\{a_1,b_1,a_2,b_2......a_n,b_n\}$ 。
不知道为什么闭括号显示不出来，见鬼了！
这里A用尾插法，B用头插法即可。注意这里一定要用引用传值，否则会报错。

LinkList Segment(LinkList C, LinkList& A, LinkList& B){
    LNode* hc = C->next;
    A =(LNode*)malloc(sizeof(LNode));  // A的表头
    B =(LNode*)malloc(sizeof(LNode));  // B的表头
    A->next = NULL;
    B->next = NULL;
    LNode* ra = A;
    int i = 0;
    while(hc != NULL){
        if(i % 2 == 0){
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = hc->data;
            new_node->next = NULL;
            ra->next = new_node;
            ra = new_node;
        }
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = hc->data;
            LNode *p = B->next;
            B->next = new_node;
            new_node->next = p;
        }
        i++;
        hc = hc->next;
    }
    ra->next = NULL;
    return B;
}

两个递增的链表，将其合并为一个递减的链表，用原来两个链表的空间存放合并后的链表。

void Merge_Sort(LinkList& A, LinkList& B){  // 把A和B和在一起 放在A当中 用头插法
    LNode *r, *p = A->next;
    LNode *q = B->next;
    A->next = NULL;
    while(p&& q){
        if(p->data <= q->data){
            r = p->next;
            p->next = A->next;
            A->next = p;
            p = r;
        }
        else{
            r = q->next;
            q->next = A->next;
            A->next = q;
            q = r;
        }
    }
        // 还有一个链表有剩余元素
    if(p)
        q = p;
    while(q){
        r = q->next;
        q->next = A->next;
        A->next = q;
        q = r;
    }
    
    free(B);
}

判断循环双链表是否对称

// 循环双链表
typedef struct DNode{
    int data;
    DNode* prior;
    DNode* next;
}DNode, *DLinkList;

bool IsSymmetry(DLinkList L){
    DNode *p = L->next;  // 头节点
    DNode *q = L->prior;  // 尾结点
    while(p != q && p->next != q){
        if(p->data != q->data)
            return false;
        p = p->next;
        q = q->prior;
    }
    return true;
}

判断链表是否有环，并返回环的入口

LNode* FindLoopStart(LNode *head){
    LNode *fast = head, *slow = head;
    while(slow != NULL && fast != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            break;
    }
    if(slow == NULL || fast->next == NULL)
        return NULL;
    LNode *p1 = head;  // 表头
    LNode *p2 = slow;  // 相遇点
    while(p1 != p2){
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

找到一个链表的中点
利用双指针，一个快一个慢，当快指针到了尾部的时候，满指针刚好到中间。以下代码中，mid其实到了((high+low)/2)向上取整的位置

ListNode* findMid(ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast->next != NULL && fast->next->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

链表归并排序

ListNode* sortList(ListNode* head) {
    return sortList(head, NULL);
}

ListNode* Merge(ListNode* l1, ListNode* l2){
    ListNode* l = new ListNode(0);
    ListNode* p = l1;
    ListNode* q = l2;
    ListNode* node = l;
    while(p != NULL && q != NULL){
        if(p->val < q->val){
            node->next = p;
            p = p->next;
        }
        else{
            node->next = q;
            q = q->next;
        }
        node = node->next;
    }
    if(p != NULL){
        node->next = p;
       
    }
    if(q != NULL){
        node->next = q;
    }
    return l->next;
}
ListNode* sortList(ListNode* head, ListNode* tail) {
    if(head == NULL)
    return NULL;
    if(head->next == tail){  // 前面已经排过序了 递归返回的时候 两边都带有mid
        head->next = NULL;
        return head;
    }
    ListNode* slow=head, *fast=head;
    // 设置快慢指针 找到中点的位置
    while(fast != tail){  // 不能用NULL来当判断条件 因为后面可能还有节点
        slow = slow->next;
        fast = fast->next;
        if(fast != tail)
        fast = fast->next;
    }
    ListNode* mid = slow;  // mid其实到了((high+low)/2)向上取整的位置
    return Merge(sortList(head, mid),sortList(mid, tail));
}

总结

如果要求将新生成的链表存放在原来的链表当中，比如对A和B进行某种处理，将最终结果放在A中，一般的处理方法如下：（如第7题）

记录A->next = p，然后用p作为工作指针去遍历A中的所有元素
将A置空，如果有元素符合题目要求，将这个元素用尾插法插入A表

最后编辑于：2021.10.18 11:02:18

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 200,045评论 5赞 468
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,114评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 147,120评论 0赞 332
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 53,902评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 62,828评论 5赞 360
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,132评论 1赞 277
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,590评论 3赞 390
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,258评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,408评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,335评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,385评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,068评论 3赞 315
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,660评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,747评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,967评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,406评论 2赞 346
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 41,970评论 2赞 341

数据结构｜有关链表的练习题

链表定义

有关链表的一些基础函数

总结

推荐阅读更多精彩内容