数据结构-5-链表面试题

骑猪看日落 2022-05-27 02:35 213阅读 0赞

#                                              数据结构-5-链表面试题 #

从尾到头打印单链表 
    删除一个无头单链表的非尾节点（不能遍历链表） 
    在无头单链表的一个节点前插入一个节点（不能遍历链表） 
    单链表实现约瑟夫环(JosephCircle) 
    逆置/反转单链表 
    单链表排序（冒泡排序&快速排序） 
    合并两个有序链表,合并后依然有序 
    查找单链表的中间节点，要求只能遍历一次链表 
    查找单链表的倒数第k个节点，要求只能遍历一次链表 
    删除链表的倒数第K个结点 
    判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算 
    每个算法的时间复杂度&空间复杂度。 
    判断两个链表是否相交，若相交，求交点。（假设链表不带环） 
    判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】 
    复杂链表的复制。一个链表的每个节点，有一个指向next指针指向 
    下一个节点，还有一个random指针指向这个链表中的一个随机节点 
    或者NULL，现在要求实现复制这个链表，返回复制后的新链表。 
    求两个已排序单链表中相同的数据。

//函数实现部分
    #pragma once
    #include<stdio.h>
    #include<Windows.h>
    #include<assert.h>
    
    #define  Datatype int
    typedef struct SlistNode
    {
        struct SlistNode*next;
        Datatype x;
    }SlistNode;
    
    SlistNode* BuySlist(Datatype x)
    {
        SlistNode*node = (SlistNode*)malloc(sizeof(SlistNode));
        assert(node);
        node->x = x;
        node->next = NULL;
        return node;
    }
    
    void SlistPushBack(SlistNode**pphead,Datatype x)
    {
        if (NULL == *pphead)
        {
            *pphead = BuySlist(x);
        }
        else
        {
            SlistNode*cur = *pphead;
            while (cur->next)
                cur = cur->next;
            cur ->next= BuySlist(x);
        }
    }
    void SlistPrint(SlistNode*phead)
    {
        SlistNode*cur = phead;
        if (phead == NULL)
            return;
        while (cur)
        {
            printf("%d->", cur->x);
            cur = cur->next;
        }
        printf("NULL\n");
    }
    void SlistPrintTailToHead(SlistNode* phead)//从尾到头打印单链表非递归
    {
        SlistNode*end = NULL;
        while (end != phead)
        {
            SlistNode*cur = phead;
            while (cur->next != end)
                cur = cur->next;
            printf("%d ", cur->x);
            end = cur;
        }
        printf("\n");
    }
    
    void PrintTailToHeadR(SlistNode* head)//从尾到头打印单链表递归法
    {
        if (head == NULL)
            return;
    
        PrintTailToHeadR(head->next);
        printf("%d ", head->x);
    }
    SlistNode* SlistFind(SlistNode*ps,Datatype x)
    {
        SlistNode*cur = ps;
        while (cur)
        {
            if (cur->x == x)
                return cur;
            cur = cur->next;
        }
        return NULL;
    }
    
    void SlistDelNonTailNode(SlistNode* pos)//删除一个无头单链表的非尾节点（不能遍历链表）
    {
        //替换法
        assert(pos&&pos->next);
        SlistNode*npos = pos->next;
        pos->x = npos->x;
        pos->next = npos->next;
        free(npos);
        npos = NULL;
    }
    
    void SlistInsertFront(SlistNode* pos, Datatype x)//在无头单链表的一个节点前插入一个节点（不能遍历链表）
    {
        SlistNode*newnode = (SlistNode*)malloc(sizeof(SlistNode));
        assert(newnode&&pos);
        newnode->x = pos->x;
        newnode->next = pos->next;
        pos ->x=x;
        pos->next = newnode;
    }
    
    void SlistErase(SlistNode**phead,SlistNode*pos)
    {
        SlistNode *cur = *phead;
        if ((*phead) == NULL || pos == NULL)
            ;
        while (cur->next != pos)
            cur = cur->next;
        cur->next = pos->next;
        free(pos);
        pos = NULL;
    }
    SlistNode* SlistJosephCircle(SlistNode*phead, int k)//单链表实现约瑟夫环(JosephCircle)
    {
        SlistNode*cur =phead;
        SlistNode*tail = phead;
        if (phead == NULL)
            return NULL;
        //构成环
        while (tail->next != NULL)
            tail = tail->next;
        tail->next = phead;
        while (cur->next != cur)
        {
            SlistNode*next = cur->next;
            int count = k;
    
            while (--count)
                cur = cur->next;
    
            cur->x = next->x;
            cur->next = next->next;
    
            free(next);
        }
        return cur;
    }
    
    
    SlistNode* SlistReverse1(SlistNode* list)//就地逆置 / 反转单链表
    {
        SlistNode*n1, *n2, *n3;
        if (list == NULL || list->next == NULL)
            return list;
        n1= list;
        n2 = n1->next;
        n3 =n2->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;
        }
        //到这里n2为空了，n1成了最后一个结点。
        list->next = NULL;
        list = n1;
        return list;
    }
    SlistNode*SlistReverse2(SlistNode*s)//头插式逆置
    {
        SlistNode*new = NULL;
        SlistNode*cur = s;
        while (cur)
        {
            SlistNode*tmp = cur;//拿来了s的第cur个结点放在tmp结点
            cur = cur->next;
            //把拿来的结点头插到new里
            tmp->next = new;
            new =tmp;
        }
        return new;
    }
    
    
    void Swap(size_t *a,size_t *b)
    {
        (*a) ^= *b;
        (*b) ^= *a;
        (*a) ^= *b;
    }
    void SlistBubbleSort(SlistNode* list)//单链表排序（冒泡排序&快速排序）
    {
        SlistNode*tail = NULL, *cur = list;
        if (list == NULL || list->next == NULL)
            return;
        while (tail != list)
        {
            int flag = 0;
            SlistNode*next = cur->next;
            while (next != NULL)
            {
                if (cur->x > next->x)
                {
                    Swap(&cur->x, &next->x);
                    flag = 1;
                }
                cur = cur->next;
                next = next->next;
            }
            if (flag == 0)
                break;
            tail = cur;
        }
    }
    
    
    SlistNode* SlistMerge(SlistNode* list1, SlistNode* list2)// 升序 //合并两个有序链表, 合并后依然有序
    {
        SlistNode*cur1 = list1;
        SlistNode*cur2 = list2;
        SlistNode*new =NULL;
        SlistNode*newtail = NULL;
        if (cur1 == NULL)
            return cur2;
        if (cur2 == NULL)
            return cur1;
        if (cur1->x < cur2->x)
        {
            new = cur1;
            cur1 = cur1->next;
        }
        else
        {
            new = cur2;
            cur2 = cur2->next;
        }
        newtail = new;
        while (cur1&&cur2)
        {
            if (cur1->x < cur2->x)
            {
                newtail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                newtail->next = cur2;
                cur2 = cur2->next;
            }
            newtail = newtail->next;
        }
        if (cur1)
            newtail->next = cur1;
        if (cur2)
            newtail->next = cur2;
        return new;
    }
    SlistNode* SlistFindMidNode(SlistNode* list)//查找单链表的中间节点，要求只能遍历一次链表
    {
        SlistNode*slow = list, *fast = list->next->next;//fast先走
        if (list == NULL||list->next==NULL)
            return list;
    
        while (fast)
        {
            slow = slow->next;
            fast = fast->next;
            if (fast)
                fast = fast->next;
        }
        return slow;
    }
    
    
    SlistNode* SlistFindTailKNode(SlistNode* list, int k)//查找单链表的倒数第k个节点，要求只能遍历一次链表
    {
        SlistNode*slow, *fast;
        slow = fast =list;
        while (k--)
        {
            if (fast == NULL)
                return NULL;
            fast = fast->next;
        }
        while (fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
    
    
    
    void DelTailK(SlistNode**p, int k)//删除链表的倒数第K个结点
    {
        SlistNode*tmp=SlistFindTailKNode(*p, k);
        SlistNode*prev = *p, *cur = prev->next;
        while (prev!=tmp)
        {
            prev = prev->next;
            cur = cur->next;
        }
        prev->next = cur->next;
        free(cur);
        cur = NULL;
    }
    
    
    SlistNode* SlistIsCycle(SlistNode* list)// 链表带环问题 //判断单链表是否带环？
    {
        SlistNode*slow=list, *fast=list;
        while (fast&&fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow)
                return fast;
        }
        return NULL;
    }
    
    
    SlistNode* SlistEntryNode(SlistNode* list, SlistNode* meet)//求环的入口点？
    {
        while (list != meet)
        {
            list = list->next;
            meet = meet->next;
        }
        return meet;
    }
    
    
    int SlistCycleLen(SlistNode*entry,SlistNode* meet)//若带环，求环的长度？
    {
        int len = 1;
        while (meet != entry)
        {
            entry = entry->next;
            len++;
        }
        entry = entry->next;
        while (meet != entry)
        {
            entry = entry->next;
            len++;
        }
        return len;
    }
    
    
    
    // 链表相交问题 
    int SlistIsCrossNode(SlistNode* list1, SlistNode* list2)//判断两个链表是否相交
    {
        SlistNode*cur1=list1, *cur2=list2;
        while (cur1->next)
            cur1 = cur1->next;
        while (cur2->next)
            cur2 = cur2->next;
        if (cur1 == cur2)
            return 1;
        else
            return 0;
    }
    
    SlistNode* SlistCrossNode(SlistNode* list1, SlistNode* list2)//若相交，求交点。（假设链表不带环）
    {
        int len1 = 0, len2 = 0, gap = 0;
        SlistNode*shortlist=list2, *longlist=list1;
        SlistNode*cur1 = list1, *cur2 = list2;
        while (cur1)
        {
            ++len1;
            cur1 = cur1->next;
        }
        while (cur2)
        {
            ++len2;
            cur2 = cur2->next;
        }
    
    
        if (len1 < len2)
        {
            longlist = list2;
            shortlist = list1;
        }
        gap = abs(len1 - len2);
        while (gap--)
            longlist = longlist->next;
        while (longlist != shortlist)
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
        return shortlist;
    }
    
    
    void UnionSet(SlistNode* list1, SlistNode* list2);//求两个已排序单链表中相同的数据。
    void UnionSet(SlistNode*list1, SlistNode*list2)
    {
        assert(list1&&list2);
        SlistNode*cur1 = list1;
        SlistNode*cur2 = list2;
        while (cur1 && cur2)
        {
            if (cur1->x == cur2->x)
            {
                printf("%d\n", cur1->x);
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            else if (cur1->x < cur2->x)
                cur1 = cur1->next;
            else
                cur2 = cur2->next;
        }
    }
    
    // 复杂链表复制 
    typedef struct ComplexListNode
    {
        int data;
        struct ComplexListNode* next;
        struct ComplexListNode* random;
    }ComplexListNode;
    
    
    void ComplexListPrint(ComplexListNode*list)
    {
        ComplexListNode*cur = list;
        while (cur)
        {
            if (cur->random==NULL)
            {
                printf("%d:NULL", cur->data);
                cur = cur->next;    
            }
            else
            {
                printf("%d:%d ", cur->data,cur->random->data);
                cur = cur->next;
            }
        }
    }
    ComplexListNode* BuyComplexNode(int x)
    {
        ComplexListNode*newnode = (ComplexListNode*)malloc(sizeof(ComplexListNode));
        assert(newnode);
    
        newnode->data = x;
        newnode->next = NULL;
        newnode->random = NULL;
    
        return newnode;
    }
    ComplexListNode* CopyComplexList(ComplexListNode* list);//复杂链表的复制。一个链表的每个节点，有一个指向next指针指向
    //下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。
    ComplexListNode* CopyComplexList(ComplexListNode*list)
    {
        ComplexListNode*new = NULL, *tail = NULL;
        //1、逐个复制结点
        ComplexListNode*cur = list;
        if (cur == NULL)
            return NULL;
        while (cur)
        {
            ComplexListNode*newnode = BuyComplexNode(cur->data);
            ComplexListNode*next = cur->next;
    
            cur->next = newnode;
            newnode->next=next;
    
            cur = newnode->next;
        }
    
        //2、置random
        cur = list;
        while (cur)
        {
            ComplexListNode*copy = cur->next;
            if (cur->random == NULL)
            {
                copy->random = NULL;
                cur = cur->next->next;
            }
            else
            {
                copy->random = cur->random->next;
                cur = cur->next->next;
            }
        }
        //3、拆开,分别链起来
        new = tail = list->next;
        list->next = new->next;
        cur = list->next;
        while (cur)
        {
            ComplexListNode*copy=cur->next;
            cur->next = copy->next;
    
            tail->next = copy;
            tail = copy;
    
            cur = cur->next;
        }
        return new;
    }
    
      
       
        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
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75
        76
        77
        78
        79
        80
        81
        82
        83
        84
        85
        86
        87
        88
        89
        90
        91
        92
        93
        94
        95
        96
        97
        98
        99
        100
        101
        102
        103
        104
        105
        106
        107
        108
        109
        110
        111
        112
        113
        114
        115
        116
        117
        118
        119
        120
        121
        122
        123
        124
        125
        126
        127
        128
        129
        130
        131
        132
        133
        134
        135
        136
        137
        138
        139
        140
        141
        142
        143
        144
        145
        146
        147
        148
        149
        150
        151
        152
        153
        154
        155
        156
        157
        158
        159
        160
        161
        162
        163
        164
        165
        166
        167
        168
        169
        170
        171
        172
        173
        174
        175
        176
        177
        178
        179
        180
        181
        182
        183
        184
        185
        186
        187
        188
        189
        190
        191
        192
        193
        194
        195
        196
        197
        198
        199
        200
        201
        202
        203
        204
        205
        206
        207
        208
        209
        210
        211
        212
        213
        214
        215
        216
        217
        218
        219
        220
        221
        222
        223
        224
        225
        226
        227
        228
        229
        230
        231
        232
        233
        234
        235
        236
        237
        238
        239
        240
        241
        242
        243
        244
        245
        246
        247
        248
        249
        250
        251
        252
        253
        254
        255
        256
        257
        258
        259
        260
        261
        262
        263
        264
        265
        266
        267
        268
        269
        270
        271
        272
        273
        274
        275
        276
        277
        278
        279
        280
        281
        282
        283
        284
        285
        286
        287
        288
        289
        290
        291
        292
        293
        294
        295
        296
        297
        298
        299
        300
        301
        302
        303
        304
        305
        306
        307
        308
        309
        310
        311
        312
        313
        314
        315
        316
        317
        318
        319
        320
        321
        322
        323
        324
        325
        326
        327
        328
        329
        330
        331
        332
        333
        334
        335
        336
        337
        338
        339
        340
        341
        342
        343
        344
        345
        346
        347
        348
        349
        350
        351
        352
        353
        354
        355
        356
        357
        358
        359
        360
        361
        362
        363
        364
        365
        366
        367
        368
        369
        370
        371
        372
        373
        374
        375
        376
        377
        378
        379
        380
        381
        382
        383
        384
        385
        386
        387
        388
        389
        390
        391
        392
        393
        394
        395
        396
        397
        398
        399
        400
        401
        402
        403
        404
        405
        406
        407
        408
        409
        410
        411
        412
        413
        414
        415
        416
        417
        418
        419
        420
        421
        422
        423
        424
        425
        426
        427
        428
        429
        430
        431
        432
        433
        434
        435
        436
        437
        438
        439
        440
        441
        442
        443
        444
        445
        446
        447
        448
        449
        450
        451
        452
        453
        454
        455
        456
        457
        458
        459
        460
        461
        462
        463
        464
        465
        466
        467
        468
        469
        470
        471
        472
        473
        474
        475
        476
        477
        478
        479
        480
        481
        482
        483
        484
        485
        486
        487
        488
        489
        490
        491
        492
        493
        494
        495
        496
        497
        498
        499
        500
        501
        502
        503
        504
        505
        506

//测试部分
    #include"Slist.h"
    void test1();
    void test1()//测试尾打印
    {
        SlistNode*s=NULL;
        SlistPushBack(&s, 0);
        SlistPushBack(&s, 1);
        SlistPushBack(&s, 2);
        SlistPushBack(&s, 3);
        SlistPushBack(&s, 4);
        SlistPushBack(&s, 5);
        //SlistPrint(s);
        //PrintTailToHeadR(s);
        SlistPrintTailToHead(s);
        SlistNode*p = SlistFind(s, 4);
        SlistDelNonTailNode(p);
        SlistPrintTailToHead(s);
    }
    
    void test2();
    void test2()//测试无头链表pos前插入x，时间复杂度小O（n)
    {
        SlistNode*p = NULL;
        SlistNode*list = NULL;
        SlistPushBack(&list, 5);
        SlistPushBack(&list, 2);
        SlistPushBack(&list, 1);
        SlistPushBack(&list, 99);
        SlistPrint(list);
        p = SlistFind(list,99);
        SlistInsertFront(p,1314);
    
        SlistPrint(list);
    }
    
    void test3();
    void test3()//杰耶夫环谁死问题
    {
        SlistNode*p = NULL;
        SlistNode*s = NULL;
        SlistPushBack(&s, 1);
        SlistPushBack(&s, 2);
        SlistPushBack(&s, 3);
        SlistPushBack(&s, 4);
        SlistPushBack(&s, 5);
        SlistPushBack(&s, 6);
        SlistPrint(s);
        p = SlistJosephCircle(s, 3);
        printf("%d\n", p->x);
    }
    
    void test4();
    void test4()//逆置单链表
    {
        SlistNode*tmp;
        SlistNode*s = NULL;
        SlistPushBack(&s, 1);
        SlistPushBack(&s, 2);
        SlistPushBack(&s, 3);
        SlistPushBack(&s, 4);
        SlistPushBack(&s, 5);
        SlistPushBack(&s, 6);
        SlistPrint(s);
        tmp=SlistReverse2(s);
        SlistPrint(tmp);
    }
    
    void test5();
    void test5()//冒泡排序
    {
        SlistNode*s = NULL;
        SlistPushBack(&s, 11);
        SlistPushBack(&s, 2);
        SlistPushBack(&s, 13);
        SlistPushBack(&s, 24);
        SlistPushBack(&s, 59);
        SlistPushBack(&s, 76);
        SlistPrint(s);
        SlistBubbleSort(s);
        SlistPrint(s);
    }
    
    void test6();
    void test6()//测试两个有序链表合并成一个有序链表
    {
        SlistNode*s1 = NULL;
        SlistNode*s2 = NULL;
        SlistNode*s = NULL;
        SlistPushBack(&s1, 1);
        SlistPushBack(&s1, 2);
        SlistPushBack(&s1, 3);
        SlistPushBack(&s2, 2);
        SlistPushBack(&s2, 6);
        SlistPushBack(&s2, 7);
        SlistPushBack(&s2, 110);
        SlistPrint(s1);
        SlistPrint(s2);
        s = SlistMerge(s1, s2);
        SlistPrint(s);
    
        printf("%d\n",SlistFindMidNode(s)->x);
    
    }
    
    void test7();
    void test7()//找倒数第k个数并且删除倒数第k个数
    {
        SlistNode*s=NULL;
        SlistPushBack(&s, 199);
        SlistPushBack(&s, 26);
        SlistPushBack(&s, 364);
        SlistPushBack(&s, 214);
        SlistPushBack(&s, 65);
        SlistPushBack(&s, 56);
        printf("%d\n",SlistFindTailKNode(s, 2)->x);
        DelTailK(&s, 3);
        SlistPrint(s);
    }
    
    void TestCycle();
    void TestCycle()//链表带环问题测试
    {
        SlistNode*list = NULL;
        SlistNode* pos, *tail, *meet,*entry;
        SlistPushBack(&list, 1);
        SlistPushBack(&list, 2);
        SlistPushBack(&list, 3);
        SlistPushBack(&list, 4);
        SlistPushBack(&list, 5);
        SlistPushBack(&list, 6);
        tail = SlistFind(list, 6);
        pos = SlistFind(list, 4);
        tail->next = pos;
        meet = SlistIsCycle(list);
        entry=SlistEntryNode(list, meet);
        printf("%d\n",meet->x);
        printf("%d\n", entry->x);
        printf("%d\n", SlistCycleLen(entry, meet));
    }
    
    void SlistCorss();
    void SlistCross()
    {
        SlistNode*list1=NULL;
        SlistNode*list2=NULL;
        SlistNode*pos1, *pos2;
        SlistPushBack(&list1, 1);
        SlistPushBack(&list1, 2);
        SlistPushBack(&list1, 3);
    
        SlistPushBack(&list2, 9);
        SlistPushBack(&list2, 8);
        SlistPushBack(&list2, 4);
    
        pos1 = SlistFind(list1, 3);
        pos2 = SlistFind(list2, 8);
        pos1->next = pos2;
        printf("%d\n", SlistIsCrossNode(list1, list2));
        printf("%d\n",SlistCrossNode(list1, list2)->x);
    }
    
    void ComplexListNodeTest()
    {
        ComplexListNode*copylist=NULL;
        ComplexListNode*n1 = BuyComplexNode(1);
        ComplexListNode*n2 = BuyComplexNode(2);
        ComplexListNode*n3 = BuyComplexNode(3);
        ComplexListNode*n4 = BuyComplexNode(4);
    
        n1->next = n2;
        n2->next = n3;
        n3->next = n4;
        n4->next = NULL;
        n1->random = n3;
        n2->random = n1;
        n3->random = n3;
        n4->random = NULL;
        ComplexListPrint(n1);
        printf("\n");
        copylist=CopyComplexList(n1);
        ComplexListPrint(copylist);
    }
    
    void UnionSetTest()
    {
        SlistNode*s1=NULL,*s2=NULL;
        SlistPushBack(&s1, 0);
        SlistPushBack(&s1, 1);
        SlistPushBack(&s1, 2);
        SlistPushBack(&s1, 3);
        SlistPushBack(&s1, 4);
        SlistPushBack(&s2, 3);
        SlistPushBack(&s2, 4);
        SlistPushBack(&s2, 5);
        SlistPushBack(&s2, 6);
        UnionSet(s1, s2);
    }
    int main()
    {
        //test1();
        //test2();
        //test3();
        //test4();
        //test5();
        //test6();
        //test7();
        //TestCycle();
        //SlistCross();
        ComplexListNodeTest();
        //UnionSetTest();
        system("pause");
        return 0;
    }