• 链表经典面试oj题

    文章目录

    前言

    如果可以自己做出了这些链表oj题，那么说明链表基础掌握的就还行，当然，一开始不会的话也没什么，我相信学完这些题会进一步加深对链表的理解和一些技巧；

    一、移除链表元素

    在这里插入图片描述

    把节点的值和val相等的节点释放掉，再组成新的链表；
    这个时候为了方便头指针的释放，我们链表带头，因为不用考虑头是否要释放；然后再用两个指针，一前一后走，如果值不相等，就迭代走下去，代码是：tail=cur,cur=cur->next;,但是开始的时要，phead->next=head,tail=head;
    下面代码我就多了些操作，但是思路都作业，要是值相等，那么先保存该节点的下一个节点，然后free该节点，把前面一个节点和下一个节点连接起来；
    next=cur->next,free(cur),tail->next=cur=next;
    最后值得注意的是：如果最后一个或者几个都是相等的节点，那么全部free完后，最后一个不相等的节点的next还存着free掉的节点地址，所有出循环后要把最后一个节点的next赋空指针；然后就是把头free了，返回头的下一个节点；

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
if(head==NULL)
return head;
struct ListNode* phead=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail=phead,*cur=head;
while(cur){
    if(cur->val!=val){
        tail->next=cur;
        tail=tail->next;
        cur=cur->next;
    }
    else{
        struct ListNode* next=cur->next;
        free(cur);
        cur=next;
    }
}
if(tail)
tail->next=NULL;
head=phead->next;
free(phead);
phead=NULL;
return head;
}

    • 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

    二 . 反转链表

    在这里插入图片描述

    我们用三个指针，后面两个指针用于反转两个节点，最前面的指针用于保存下一个节点，便于迭代；
    这样就走起来了，prev指针在最左边，也就是后面，cur是当前，next是最前面的指针，走的时候是cur->next=prev;prev=cur;cur=next;而next则是一直向后的，所有就这样走起来了；不清楚的可以画一下图，更直观；

    struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
return head;
struct ListNode* prev=NULL,*cur=head,*next=cur;
while(next){
    next=cur->next;
    cur->next=prev;
    prev=cur;
    cur=next;
}
return prev;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    三 . 链表的中间节点

    在这里插入图片描述

    这里有奇数链表和偶数链表，奇数返回的奇数中间的节点，偶数就是第二个中间节点嘛；然后这里介绍一个方法叫做快慢指针，也许听过，这个方法用来解决这题非常简单，快指针走两步，慢指针走一步，当链表为奇数时，快指针走到fast->next==NULL的时候，慢指针就是停在了中间节点；当链表为偶数时，fast指针刚好走到空的时候，慢指针就是第二个中间节点了；

    struct ListNode* middleNode(struct ListNode* head){
struct ListNode* fast=head,*slow=head;
while(fast&&fast->next){
    fast=fast->next->next;
    slow=slow->next;
}
return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    四. 链表中倒数第k个结点

    在这里插入图片描述

    先看正常情况，思路是让一个指针先走k步，然后再和头部指针一起走，当前面指针走到空时，后面的指针指向的就是倒数第K个节点了；
    当k=0的时候，这个思路没问题；
    当k=链表长度的时候，前面的指针直接走到空了，后面的指针还在第一个节点，没问题；
    当k>链表长度的时候，这个时候就会有问题了，前面的指针会走到空了还在走，这是不对的，所以我们要让前面走k步的循环里面指针进来的里面不可以是空指针，因为空指针不可能在向后走了，直接返回空指针；

    struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* fast=pListHead,*slow=pListHead;
    while(k--){
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    while(fast){
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    五. 合并两个有序链表

    在这里插入图片描述

    还是为了方便，带个头节点，有的题带头节点是会方便很多的，我们考虑问题的时候要有加头节点的考虑哦；把两个链表中小的值的节点尾插到我们自己的链表后面，就这样一直尾插，到一个链表都尾插完后跳出循环，然后把没有插完的链表直接连接就行了；
    但是有可能两个或者其中一个链表为空，我的话单独处理；

    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL&&list2==NULL)
return NULL;
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
struct ListNode* phead=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail=phead,*head1=list1,*head2=list2;
while(head1&&head2){
    if(head1->val<head2->val){
        tail->next=head1;
        tail=tail->next;
        head1=head1->next;
    }
    else{
        tail->next=head2;
        tail=tail->next;
        head2=head2->next;
    }
}
if(head1)
tail->next=head1;
if(head2)
tail->next=head2;
struct ListNode* head=phead->next;
free(phead);
phead=NULL;
return head;
}

    • 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

    六. 链表分割

    在这里插入图片描述

    我们可以把小于x的节点组成一个链表，然后大于x的节点组成一个链表，然后把大于的链表连接到小于的链表后面就行了；不够值得注意的是，我们有要带头，把两个链表都带头，不过那么可以不带头试试，的确会更麻烦；
    还有要注意的是，链表都大于等于或者小于等于x的情况，这个时候我们的方法可以解决，不过就是把头的下一个节点置空一下就行了；还有就是大的链表的尾节点不一定是原链表的尾节点，它的next不一定指向空，所以我们需要自己把那个节点置空；

    class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //分成两个链表，一个所有值小于x的链表，另一个大于或者等于x的值的链表
        struct ListNode* pheadsmall=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* pheadgreater=(struct ListNode*)malloc(sizeof(struct ListNode));
        pheadsmall->next=NULL;//带头方便头节点问题
        pheadgreater->next=NULL;
        struct ListNode* tail=pHead,*smalltail=pheadsmall,*greatertail=pheadgreater;
        while(tail){
            if(tail->val<x){
                smalltail->next=tail;
                smalltail=smalltail->next;
                tail=tail->next;
            }
            else{
                greatertail->next=tail;
                greatertail=greatertail->next;
                tail=tail->next;
            }
        }
        smalltail->next=pheadgreater->next;
        greatertail->next=NULL;//大的链表尾节点的next不一定是空指针；
        struct ListNode* head=pheadsmall->next;
        free(pheadsmall);
        free(pheadgreater);
        pheadgreater=NULL;
        pheadsmall=NULL;
        return head;
    }
};

    • 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

    七. 链表的回文结构

    在这里插入图片描述

    两个思路，第一个就是把原链表复制一个，把复制链表反转一下，再于原链表比较，要是一样，就没错，要是有一个节点不对，那么就不是回文结构；
    第二个方法就是把把链表分成两条，前面的节点一条，中间节点后面的一条链表（包括中间节点），把后面的一条链表反转，再和前面链表对比，直到有链表到空，就是回文链表，要是有一个对不上，就不是；
    还有要注意的是，第一个思路比较多人想到的，第二个思路不好想；我就写一下第二个方法的代码；

    class PalindromeList {
public:
    struct ListNode* Getmid(struct ListNode* phead){
        struct ListNode* fast=phead,*slow=phead;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    struct ListNode* Turnslist(struct ListNode* phead){
        struct ListNode* n1=NULL,*n2=phead,*n3=phead;
        while(n2){
            n3=n3->next;
            n2->next=n1;
            n1=n2;
            n2=n3;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* phead1=Getmid(A);
        struct ListNode* phead2=Turnslist(phead1);
        while(A&&phead2){
            if(A->val!=phead2->val)
                return false;
            A=A->next;
            phead2=phead2->next;
        }
        return true;
    }
};

    • 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

    八. 相交链表

    在这里插入图片描述

    思路：要是相交，总有一个节点的地址相同，只要判断最后一个节点是否相同，那么就可以判断链表是否相交；要是相交，怎么判断第一个交点呢？
    我们可以得出两条链表长度，然后长链表先走差值步数，然后两个链表指针一起走，直到指针相等时就是第一个节点指针了；

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headB==NULL)
    return NULL;
    if(headA==NULL)
    return NULL;
    struct ListNode* tail1=headA,*tail2=headB;
    int l1=1,l2=1;
    while(tail1->next){
        ++l1;
        tail1=tail1->next;
    }
    while(tail2->next){
        ++l2;
        tail2=tail2->next;
    }
    if(tail1!=tail2)//两个链表最后一个节点不相等，那么肯定不相交
    return NULL;
    struct ListNode* longslist=headA,*shortslist=headB;
    if(l1<l2)
    {
        longslist=headB;
        shortslist=headA;
    }
    //让长的链表先走差的步数
    int n=abs(l1-l2);
    while(n--){
        longslist=longslist->next;
    }
    while(longslist!=shortslist){
        longslist=longslist->next;
        shortslist=shortslist->next;
    }
    return longslist;

}

    • 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

    九. 环形链表

    在这里插入图片描述

    判断是否带环，直接快慢指针解决，要是快慢指针相遇，那么肯定有环，要是循环可以结束，那么就不带环；

    bool hasCycle(struct ListNode *head) {
    struct ListNode* fast=head,*slow=head;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        return true;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    带环问题还有延伸的问题：快指针走两步，慢指针走一步，是否一定可以追上？要是快指针走三步，慢指针走一步，结果当如何，会相遇不？快指针走四步，慢指针 一步呢，结果又是如何？当快指针走n步，慢指针走m步，结果又如何？

    在这里插入图片描述
    在这里插入图片描述

    当fast走三步，slow走一步的情况：

    在这里插入图片描述

    在这里插入图片描述

    其它情况和上面类似，都可以解释；

    十. 环形链表 ||

    在这里插入图片描述

    两种方法；第一种：公式法，快慢指针的交点和起点一起开始走，都走一步，当相遇时，就是环的人口点；会证明；
    第二种方法：快慢指针相遇节点的下一个节点为第二条链表的起节点，原链表起点就是第一条链表起节点，把快慢指针相遇节点的next置空，然后两条链表的第一个相交节点不就是环的人口节点吗；然后看情况要不要恢复链表，不能通过就恢复链表；

    在这里插入图片描述

    //第一种方法：
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast=head,*slow=head;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast){//如果有环，可以根据公式得出人口
        //快慢指针相遇节点开始和头节点一起走，相遇点就是答案
            struct ListNode* cur1=head,*cur2=slow;
            while(cur1!=cur2){
                cur1=cur1->next;
                cur2=cur2->next;
            }
            return cur1;        
        }
    }
    return NULL;//如果出来了循环，说明不带环
}
//第二种方法：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headB==NULL)
    return NULL;
    if(headA==NULL)
    return NULL;
    struct ListNode* tail1=headA,*tail2=headB;
    int l1=1,l2=1;
    while(tail1->next){
        ++l1;
        tail1=tail1->next;
    }
    while(tail2->next){
        ++l2;
        tail2=tail2->next;
    }
    if(tail1!=tail2)//两个链表最后一个节点不相等，那么肯定不相交
    return NULL;
    struct ListNode* longslist=headA,*shortslist=headB;
    if(l1<l2)
    {
        longslist=headB;
        shortslist=headA;
    }
    //让长的链表先走差的步数
    int n=abs(l1-l2);
    while(n--){
        longslist=longslist->next;
    }
    while(longslist!=shortslist){
        longslist=longslist->next;
        shortslist=shortslist->next;
    }
    return longslist;

}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast=head,*slow=head;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast){//如果有环，可以将快慢指针相等的节点的next设置为空指针，然后本来的下一个节点变成第二个链表的头节点，这两个链表的交节点
//即是答案
            struct ListNode* cur1=head,*cur2=fast->next;
            fast->next=NULL;
            struct ListNode* dst=getIntersectionNode(cur1,cur2);
            return dst;
        }
    }
    return NULL;//如果出来了循环，说明不带环
}


    • 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

    总结

    在这里插入图片描述

  • 相关阅读:
    一文搞定Linux信号
    分布式和微服务
    LeetCode 1752. 检查数组是否经排序和轮转得到
    云原生Kubernetes之浅认知
    深究 DevOps 与平台工程的区别
    GZ035 5G组网与运维赛题第1套
    基于JavaWeb的学生成绩管理系统
    无涯教程-JavaScript - IMDIV函数
    15. SAP ABAP OData 服务里 EntityType 和 EntitySet 的区别
    几种经典的卷积神经网络
  • 原文地址：https://blog.csdn.net/qq_68844357/article/details/126485261