• 【数据结构】图文详解11道力扣链表OJ题

    一、移除链表元素

    二、反转链表

    三、链表的中间节点

    四、链表中倒数第k个节点

    五、合并两个有序列表

    六、链表分割

    七、回文链表

    八、相交链表

    九、环形链表

    十、环形链表 II

    1、思路一

    2、思路二

    十一、复制带随即指针的链表

    1、思路

    2、代码

    一、移除链表元素

    1、思路

    新建一个哨兵位，用cur指针遍历原链表，cur->val!=val,将该节点连接至哨兵链表，反之释放。迭代遍历原链表即可，最后记得将哨兵链表的尾节点的next置空！！！

    2、代码

    1. struct ListNode* removeElements(struct ListNode* head, int val){
    2.     struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
    3.     struct ListNode* guardcur=guard;//用于记录哨兵链表的尾插
    4.     struct ListNode* cur=head;//用于原链表的遍历
    5.     while(cur)
    6.     {
    7.         struct ListNode* next=cur->next;
    8.         if(cur->val!=val)
    9.         {
    10.            guardcur->next=cur;
    11.            guardcur=cur;
    12.         }
    13.         else 
    14.         {
    15.             free(cur);
    16.         }
    17.             cur=next;
    18.     }
    19.     guardcur->next=NULL;//最后需要把尾节点的next置空
    20.     head=guard->next;
    21.     free(guard);//记得释放哨兵位
    22.     return head;
    23. }

    二、反转链表

    1、思路

    遍历原链表，将每一个节点取下来，不断头插反转链表

    2、代码

    1. struct ListNode* reverseList(struct ListNode* head){
    2.     struct ListNode* cur=head;
    3.     struct ListNode* newhead=NULL;
    4.     while(cur)
    5.     {
    6.         struct ListNode* next=cur->next;
    7.         cur->next=newhead;
    8.         newhead=cur;
    9.         cur=next;
    10.     }
    11.     return newhead;
    12. }

    三、链表的中间节点

    1、思路

    思路1：可以遍历计数找中间节点

    思路2：快慢指针，快指针走两步，慢指针走一步，快指针走到尾节点或者空节点，慢指针就指向链表的中间节点

    2、代码

    1. struct ListNode* middleNode(struct ListNode* head){
    2.     struct ListNode* fast=head,*slow=head;
    3.     while(fast!=NULL&&fast->next!=NULL)
    4.     {
    5.         fast=fast->next->next;
    6.         slow=slow->next;
    7.     }
    8.     return slow;
    9. }

    注意，while循环内两个条件的顺序不能颠倒。如果颠倒，当fast为NULL时，先判断fast->next!=NULL，这是一个对空指针解引用的问题！

    四、链表中倒数第k个节点

    1、思路

    定义快慢指针，不难发现，快指针需要比慢指针快k-1步，所以先让快指针向前走k-1步，判断fast==NULL是防止原链表为空，判断fast->next=NULL是因为，后面fast=fast->next，说明k大于链表长度。

    2、代码

    1. struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    2.     struct ListNode* fast=head,*slow=head;
    3.     int tmp=k-1;//快慢指针相差的距离
    4.     while(tmp--)
    5.     {
    6.         if(fast==NULL||fast->next==NULL)//考虑下值大于节点个数的问题
    7.             return NULL;
    8.         fast=fast->next;
    9.     }
    10.     while(fast->next)
    11.     {
    12.         fast=fast->next;
    13.         slow=slow->next;
    14.     }
    15.     return slow;
    16. }

    五、合并两个有序列表

    1、思路

    创建一个哨兵节点，用两个指针分别指向原链表，将val小的节点尾插即可。记得释放哨兵位。

    2、代码

    1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    2.     struct ListNode* cur1=list1,*cur2=list2;
    3.     struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
    4.     struct ListNode* guardcur=guard;
    5.     struct ListNode* small,*big;
    6.     while(cur1!=NULL&&cur2!=NULL)
    7.     {
    8.         if(cur1->val>cur2->val)
    9.         {
    10.             small=cur2;
    11.             big=cur1;
    12.             cur2=cur2->next;
    13.         }
    14.         else
    15.         {
    16.             small=cur1;
    17.             big=cur2;
    18.             cur1=cur1->next;
    19.         }
    20.         guardcur->next=small;
    21.         guardcur=small;
    22.     }
    23.     if(cur1==NULL)
    24.     {
    25.         guardcur->next=cur2;
    26.     }
    27.     else
    28.     {
    29.         guardcur->next=cur1;
    30.     }
    31.     struct ListNode* head=guard->next;
    32.     free(guard);
    33.     return head;
    34. }

    六、链表分割

    1、思路

    创建两个哨兵位，遍历原链表，将val小于x和大于等于x的节点分别尾插至两个哨兵链表，再将两个链表连接起来。注意要把大的哨兵链表的尾指针置空。

    2、代码

    1. class Partition {
    2. public:
    3.     ListNode* partition(ListNode* pHead, int x) {
    4.         ListNode* guard1=(ListNode*)malloc(sizeof(ListNode));//哨兵位1
    5.         ListNode* guard2=(ListNode*)malloc(sizeof(ListNode));//哨兵位2
    6.         ListNode* small=guard1,*big=guard2;
    7.         ListNode* cur=pHead;//用于遍历链表
    8.         while(cur)
    9.         {
    10.             if(cur->val
    11.             {
    12.                 small->next=cur;
    13.                 small=small->next;
    14.                 cur=cur->next;
    15.             }
    16.             else
    17.             {
    18.                 big->next=cur;
    19.                 big=big->next;
    20.                 cur=cur->next;
    21.             }
    22.         }
    23.         big->next=NULL;
    24.         small->next=guard2->next;//链接两个链表
    25.         free(guard2);
    26.         pHead=guard1->next;
    27.         free(guard1);
    28.         return pHead;
    29.     }
    30. };

    七、回文链表

    1、思路

    1、找出中间节点（本文题三）

    2、对后半段进行逆置（本文题二）

    3、比对val是否相等，当逆置指针为空，比对结束

    2、代码

    1. bool isPalindrome(struct ListNode* head){
    2.     //先用快慢指针找到中间节点
    3.     struct ListNode* fast=head,*slow=head;
    4.     while(fast!=NULL&&fast->next!=NULL)
    5.     {
    6.         slow=slow->next;
    7.         fast=fast->next->next;
    8.     }
    9.     //现在slow是中间节点
    10.     //反转后半部分链表
    11.     struct ListNode* newnode=NULL;
    12.     struct ListNode* cur=slow;
    13.     while(cur)
    14.     {
    15.         struct ListNode* next=cur->next;
    16.         cur->next=newnode;
    17.         newnode=cur;
    18.         cur=next;
    19.     }
    20.     //比较
    21.     fast=head;
    22.     slow=newnode;
    23.     while(slow)//fast和slow会同时为空或slow先空
    24.     {
    25.         if(fast->val!=slow->val)
    26.             return false;
    27.         fast=fast->next;
    28.         slow=slow->next;
    29.     }
    30.     return true;
    31. }

    八、相交链表

    1、思路

    1、分别遍历链表，算出两个链表的长度。

    2、让长链表先往前走，走到和短链表一样长

    3、两个链表再同时走，走到两个指针一样即为相交点，如果走到空还没有找到，则不相交

    2、代码

    1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    2.     struct ListNode* curA=headA,*curB=headB;//用于遍历链表
    3.     int lenA=1,lenB=1;//统计A和B的长度
    4.     while(curA)
    5.     {
    6.         curA=curA->next;
    7.         ++lenA;
    8.     }
    9.     while(curB)
    10.     {
    11.         curB=curB->next;
    12.         ++lenB;
    13.     }
    14.     int a=abs(lenA-lenB);//A和B链表长度的差值
    15.     struct ListNode* longlist=headA,*shortlist=headB;//设两个节点
    16.     if(lenA//通过一个判断，让longlist指向较长的链表
    17.     {
    18.         longlist=headB;
    19.         shortlist=headA;
    20.     }
    21.     while(a--)//让较长的链表先把差值走掉
    22.     {
    23.         longlist=longlist->next;
    24.     }
    25.     while(longlist)
    26.     {
    27.         if(longlist==shortlist)
    28.             return longlist;
    29.         longlist=longlist->next;
    30.         shortlist=shortlist->next;
    31.     }
    32.     return NULL;
    33. }

    九、环形链表

    1、思路

    定义快慢指针，快指针一次走两步，慢指针一次走一步，如果相遇，说明有环，当快指针等于NULL，说明没环

    2、代码

    1. bool hasCycle(struct ListNode *head) {
    2.     //快指针一次走两步，慢指针一次走一步，快指针先进环，慢指针后进环，相对静止
    3.     //能追上说明有环，有一个指针为空说明没环
    4.     struct ListNode* fast=head,*slow=head;
    5.     while(fast&&fast->next)//这里不用判断slow是否为空，不管带不带环，slow没有机会为空
    6.     {
    7.         fast=fast->next->next;
    8.         slow=slow->next;
    9.         if(fast==slow)
    10.             return true;
    11.     }
    12.     return false;
    13. }

    十、环形链表 II

    1、思路一

    1、定义快慢指针，快指针一次走两步，慢指针一次走一步,找到相遇点（本文题九）

    2、将相遇点的后一个节点当成另一个链表的头结点，问题转化为本文题八

    2、代码

    1. struct ListNode *detectCycle(struct ListNode *head) {
    2.     //先找到相遇点
    3.     struct ListNode* fast=head,*slow=head;
    4.     while(fast&&fast->next)
    5.     {
    6.         fast=fast->next->next;
    7.         slow=slow->next;
    8.         if(fast==slow)
    9.             break;
    10.     }
    11.     if(fast==NULL||fast->next==NULL)
    12.         return NULL;
    13.  
    14.     struct ListNode* headA=fast->next;//两个链表的头结点
    15.     struct ListNode* curA=headA;//cur用于遍历统计链表长度
    16.     struct ListNode* headB=head;
    17.     struct ListNode* curB=headB;
    18.     int lenA=1,lenB=1;
    19.     while(curA!=fast)
    20.     {
    21.         curA=curA->next;
    22.         ++lenA;
    23.     }
    24.      while(curB!=fast)
    25.     {
    26.         curB=curB->next;
    27.         ++lenB;
    28.     }
    29.     struct ListNode* longlist=headA,*shortlist=headB;
    30.     if(lenA
    31.     {
    32.         longlist=headB;
    33.         shortlist=headA;
    34.     }
    35.     int a=abs(lenA-lenB);//长度的差值
    36.     while(a--)
    37.     {
    38.         longlist=longlist->next;
    39.     }
    40.     while(1)
    41.     {
    42.         if(longlist==shortlist)
    43.             return longlist;
    44.         longlist=longlist->next;
    45.         shortlist=shortlist->next;
    46.     }
    47. }

    3、思路二

    1、设进环前的长度为L，入环点到相遇点的距离为X，环的长度为R

    2、两指针相遇时，slow走的距离是L+X，fast走的距离是L+N*R+X，N为fast指针在环里绕的圈数（注意这里N一定大于等于1，因为快慢指针在环内相遇，说明快指针和慢指针相遇前，快指针起码路过了一次相遇点）（而且当慢指针进环后，快指针肯定会一圈追上慢指针，因为快指针比慢指针每次多走一步，相对静止，走一圈的距离必定追上）

    3、那么2*（L+X)=L+N*R+X，化简得L=N*R-X，再化简得L=(N-1)*R+R-X

    4、可得结论：一个指针从头结点开始走，另一个指针从相遇点开始走，那么他们会在入口处相遇

    4、代码

    1. struct ListNode *detectCycle(struct ListNode *head) {
    2.     struct ListNode* fast=head,*slow=head;//找相遇点
    3.     
    4.     while(fast!=NULL&&fast->next!=NULL)
    5.     {
    6.         fast=fast->next->next;
    7.         slow=slow->next;
    8.         if(fast==slow)
    9.             break;
    10.     }
    11.     if(fast==NULL||fast->next==NULL)
    12.         return NULL;
    13.     slow=head;
    14.     while(fast!=slow)
    15.     {
    16.         fast=fast->next;
    17.         slow=slow->next;
    18.     }
    19.     return fast;
    20. }

    十一、复制带随即指针的链表

    1、思路

    题目要求是复制一个一模一样的链表，难点在于random指针的控制

    1、在每个节点后边插入一个节点，复制对应的val

    2、再复制random指针，复制时要分空和非空情况，对于空，复制节点random为NNULL；非空，

    则为cur->next->random=cur->random->next

    3、再创建两个哨兵节点，将原链表与复制链表节点分开。

    2、代码

    1. struct Node* copyRandomList(struct Node* head) {
    2. 	struct Node* cur=head;
    3.     while(cur)//插入复制节点
    4.     {
    5.         struct Node* next=cur->next;
    6.         struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
    7.         cur->next=newnode;
    8.         newnode->val=cur->val;
    9.         cur=next;
    10.         newnode->next=cur;
    11.     }
    12.     cur=head;
    13.     while(cur)//复制random指针
    14.     {
    15.         if(cur->random==NULL)
    16.             cur->next->random=NULL;
    17.         else
    18.         {
    19.             cur->next->random=cur->random->next;
    20.         }
    21.         cur=cur->next->next;
    22.     }
    23.     //将链表复原
    24.     cur=head;
    25.     struct Node* guard=(struct Node*)malloc(sizeof(struct Node));
    26.     struct Node* guardcopy=(struct Node*)malloc(sizeof(struct Node));
    27.     guardcopy->next=NULL;
    28.     struct Node* curA=guard,*curB=guardcopy;
    29.     int count=1;
    30.     while(cur)
    31.     {
    32.         struct Node* next=cur->next;
    33.         if(count%2==1)
    34.         {
    35.             curA->next=cur;
    36.             curA=cur;
    37.         }
    38.         else
    39.         {
    40.             curB->next=cur;
    41.             curB=cur;
    42.         }
    43.         cur=next;
    44.         ++count;
    45.     }
    46.     curA->next=NULL;
    47.     struct Node* newhead=guardcopy->next;
    48.     free(guardcopy);
    49.     free(guard);
    50.     return newhead;
    51. }
  • 相关阅读:
    患上肝内胆管结石症状有哪些？
    数据库——集群与读写分离 ＜---＞设计优化【补】
    竞赛无人机搭积木式编程（四）---2023年TI电赛G题空地协同智能消防系统（无人机部分）
    力扣每日一题 自定义字符串排序
    springboot源码理解三、自动配置(第三方依赖中的bean)
    跑得“快”还要走得“稳”，看头部车企数字化实践怎么做
    Gradle系列——Gradle文件操作，Gradle依赖（基于Gradle文档7.5）day3-1
    系统介绍浏览器缓存机制及前端优化方案
    荣耀手机如何开启地震预警功能
    已解决 TypeError: Fetch argument None has invalid type ＜class ‘NoneType‘＞
  • 原文地址：https://blog.csdn.net/gfdxx/article/details/126318887