手撕链表OJ

????!!??‧✧̣̥̇‧✦??‧✧̣̥̇‧✦ ??‧✧̣̥̇:Solitary-walk

      ⸝⋆   ━━━┓
     - 个性标签 - ：来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━  ➴ ⷯ

本人座右铭 ：   欲达高峰,必忍其痛;欲戴王冠,必承其重。

??????? 
???自???
???信???
???　???    希望在看完我的此篇博客后可以对你有帮助哟

???????   
???????

目录：
一 ​​​​​​移除链表元素
二：反转一个单链表
三：链表的中间结点
四：链表中倒数第k个结点
五：合并两个有序链表
六：链表分割
七：链表的回文结构
八：相交链表

题目：

九： 环形链表
十：环形链表 II

 十一：

 1： ​​​​​​移除链表元素

思路分析 

这里咱有2中方法可以实现：

方法1：直接在原链表进行删除

总的方向：把等于val 的对应节点直接删除即可，定义三个指针：pre(当前指针的前一个节点),del（要删除的节点),cur（当前节点）

注意细节：

1）当链表第一个节点就需要删除 也就是说  pre == NULL,这时候头结点需要更新

2）正常情况的删除:改变pre指向节点的next ,这时候需要找到删除cur这个节点的前一个节点也就是pre

3非头结点并且也不需要删除：pre依次改变   即 pre = cur

对应草图如下：

OJ代码
  1. struct ListNode* removeElements(struct ListNode* head, int val)
  2.  {
  3.     struct ListNode* cur = head,*pre = NULL,*del = NULL;
  4.     while(cur)
  5.     {
  6.         if(cur->val == val)
  7.         {
  8.             if(pre == NULL)//头结点的删除
  9.             {
  10.                 del = cur;
  11.                 cur = del->next;
  12.               head = cur;//更新头结点
  13.                 free(del);
  14.             }
  15.             else
  16.             {
  17.                 del= cur;
  18.                 cur = del->next;
  19.                 pre->next = cur;
  20.                 free(del);
  21.         
  22.             }
  23.             
  24.         }
  25.         else
  26.         {
  27.             //不需删除
  28.             pre = cur;
  29.             cur = cur->next;
  30.  
  31.         }
  32.     }
  33.     return head;
  34. }

方法2：借助链表尾插函数的思想，把不为 val对应的节点取下来进行尾插

那么问题来了：每次尾插之前都需要先找尾，在时间上就很不占优势n个节点那么对应时间复杂度就是 O(N^2) 

这里我们就需要定义一个tail指针，以此解决此问题

总的方向：不是val的节点拿下来尾插，定义三个指针  tail(尾指针) newhead(新的头结点)cur(指向原链表的当前节点)

注意细节：

1）第一个节点不为val ：执行逻辑是赋值  newhead =tail =  cur; cur = cur->next;  tail->next = NULL;

2) 接下来就是尾插的逻辑，只需要更新尾结点即可  tail ->next = cur; tail = tail->next; cur = cur->next; tail->next = NULL;(注意这2句代码顺序不能颠倒) 

草图见下：

OJ完整代码：
  1. struct ListNode* removeElements(struct ListNode* head, int val)
  2. {    
  3.  //方法2：尾插
  4.     struct ListNode* tail = NULL,*newhead = NULL,*cur = head;
  5.     if(head == NULL)
  6.     return NULL;
  7.     while(cur)
  8.     {
  9.         if(cur->val != val )
  10.         {
  11.             if(newhead == NULL)  //第一次尾插
  12.             {
  13.                 newhead = tail =  cur;
  14.                 cur = cur->next;
  15.                 tail->next = NULL;
  16.             }
  17.             else
  18.             {
  19.                 tail->next = cur;
  20.                 tail = tail->next;//尾结点更新
  21.                 cur = cur->next;
  22.                 tail->next = NULL;//注意以上2句代码位置不能颠倒
  23.             }
  24.         }
  25.         else
  26.         {
  27.             struct ListNode* del  = cur;
  28.             cur = cur->next;
  29.             free(del);
  30.         }
  31.     }
  32.     return newhead;
  33. }

2：反转一个单链表

题目：

 思路分析

对于这题，咱也就是说，不仅仅局限于一种思维，咱格局打开 

方法1：三指针玩法（说白了，就是改变指针走向的问题）

总的方向：定义三个指针 n1 = NULL ; n2 = head; n3 = head->next ;

注意细节：

1）当链表为空的时候 

n3 = head->next; 这不就出现野指针问题了吗

合理的操作应该是：

if(head == NULL)

    return NULL;

2）循环结束条件的判断： 

3）新的头结点的返回

草图见下：

 OJ代码：
  1. struct ListNode* reverseList(struct ListNode* head) {
  2.     // struct ListNode* n1= NULL,*n2 = head,n3 = n2->next;//可能只有一个节点，此时n3是野指针
  3. struct ListNode* n1= NULL,*n2 = head ;
  4. if(head == NULL)//没有节点
  5. return NULL;
  6. if(head->next == NULL) //只有一个节点
  7. return head;
  8.     struct ListNode*n3 = n2->next;
  9.  
  10. while(n2)
  11. {
  12.      n2->next = n1;
  13.     n1 = n2;
  14.     n2 = n3;
  15.     if(n3)
  16.     n3 = n3->next;
  17. }
  18.    return n1; 
  19. }

 方法2：利用头插的思想，定义2个指针  newhead = NULL,cur = head;

  1. struct ListNode* reverseList(struct ListNode* head) {
  2.  
  3. struct ListNode*  newhead = NULL,*cur = head;
  4. if(head == NULL)
  5. return NULL;
  6. while(cur)
  7. {
  8.     struct ListNode * Next = cur->next;//保留cur的下一个节点，避免找不到
  9.     cur->next = newhead;
  10.     newhead = cur;//新的头结点
  11.      cur = Next;
  12. }
  13. return newhead;
  14. }
3：链表的中间结点

 思路分析

 采用快慢指针（fas指针走2步，slow指针走1步）

原理：在速度上fast永远是slow的2倍，所以当fast走到头的时候slow刚好走到链表的一半，slow所指向的节点就是链表的中间节点

 OJ代码：
  1. struct ListNode* middleNode(struct ListNode* head) 
  2. {
  3.     if(head == NULL)
  4.     return NULL;
  5.     struct ListNode* fast = head,*slow = head;
  6.     while(fast && fast->next)//逻辑必须是且的关系
  7.     {
  8.         fast = fast->next->next;
  9.         slow = slow->next;
  10.     }
  11.     return slow;
  12. }
4：链表中倒数第k个结点

题目：

思路讲解： 

方法1：快慢指针（注意这个与上面又有区别只不过思想是一致的） 

1）定义2个指针 fast,slow

2）先让fast指针走k步：利用循环来实现

3）再让2个指针一起走：fast走1步，slow走1步

fast = fast->next->next;

slow = slow->next; 

OJ代码：
  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
  2.     // write code here
  3.     struct ListNode* fast = pListHead,*slow = pListHead,*cur = pListHead;
  4.     if(pListHead ==NULL)
  5.     return NULL;
  6.     int count = 0;
  7.     while(cur)//先求出链表长度
  8.     {
  9.         count++;
  10.         cur = cur->next;
  11.     }
  12.     if(k > count || k == 0)
  13.     return NULL;
  14.     while(k--)
  15.     {
  16.         fast = fast->next; 
  17.     }
  18.  
  19.     while(fast)
  20.     {
  21.         fast = fast->next;
  22.         slow = slow->next;
  23.     }
  24.     return slow;
  25. }
5：合并两个有序链表

题目：

思路分析： 

比较val ，取小的进行尾插

1：定义一个head 指针，一个tail 指针（免去了每一次尾插都需要找尾结点）

2：注意临界条件的判断

草图见下：

OJ代码：
  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
  2.     
  3.     struct ListNode* head = NULL,*tail = NULL;
  4.     if( list1 == NULL&& list2 == NULL)
  5.     return NULL;
  6.     if(list1 == NULL)
  7.     return list2;
  8.     if(list2 == NULL)
  9.     return list1;
  10.     while(list1 && list2 )
  11.     {
  12.         if(list1->val >= list2->val) 
  13.         {
  14.             if(tail == NULL) //第一次尾插
  15.             {
  16.              head = tail= list2;
  17.              list2 = list2->next;
  18.              tail->next = NULL;
  19.             }
  20.             else
  21.             {
  22.              tail->next = list2;
  23.              tail = tail->next;
  24.              if(list2)
  25.               list2 = list2->next;
  26.              tail->next = NULL;//尾结点更新
  27.                 
  28.             }
  29.         }
  30.         else
  31.         {
  32.              if(tail == NULL) //第一次尾插
  33.             {
  34.              head = tail= list1;
  35.              list1 = list1->next;
  36.              tail->next = NULL;
  37.             }
  38.             else
  39.             {
  40.             tail->next = list1;
  41.              tail = tail->next;
  42.              if(list1)
  43.             list1 = list1->next;
  44.              tail->next = NULL;//尾结点更新 
  45.             }
  46.         }
  47.     }
  48.     if(list1 != NULL)
  49.     {
  50.         tail->next = list1;
  51.     }
  52.     if(list2 != NULL)
  53.     {
  54.         tail->next = list2;
  55.  
  56.     }
  57.     return head;
  58. }
6：链表分割

题目：

 思路分析

首先定义2个哨兵位 ： smallHead (指向小于 x值的对应链表）  bigHead(指向大于 x值的对应链表) 避免了空指针的问题

同时方便我们尾插进来找尾结点 定义2个尾指针 smallTail   bigTail

小于 x 进行尾插在 smallTail 

大于 x进行尾插在bigTail

最后把 2个链表进行连接

 草图见下

OJ代码
  1. class Partition {
  2. public:
  3. ListNode* partition(struct ListNode* pHead, int x)
  4. {
  5.     // write code here
  6.     /*
  7.     思路：这两个链表一定要带哨兵位
  8.     小于 x 的尾插到 一个链表
  9.     大于等于 X 的尾插到另一个链表上
  10.     对尾插的节点进行连接
  11.      */
  12.     struct ListNode* smallHead = nullptr, * smallTail = nullptr, * bigHead = nullptr, * bigTail = nullptr;//定义2个哨兵位
  13.     struct ListNode* cur = pHead;
  14.     smallHead = (struct ListNode*)malloc(sizeof(struct ListNode));
  15.     bigHead = (struct ListNode*)malloc(sizeof(struct ListNode));
  16.     smallHead->next = nullptr;
  17.     smallHead->val = -1;
  18.     bigHead->val = -1;
  19.     bigHead->next = nullptr;
  20.  
  21.     while (cur)
  22.     {
  23.         if (cur->val < x)
  24.         {
  25.             if (smallTail == nullptr)
  26.             {
  27.                 smallTail = cur;
  28.                 cur = cur->next;
  29.  
  30.                 smallTail->next = nullptr;
  31.                 smallHead->next = smallTail;
  32.             }
  33.             else
  34.             {
  35.                 smallTail->next = cur;
  36.                 cur = cur->next;
  37.  
  38.                 smallTail = smallTail->next;
  39.                 smallTail->next = nullptr;
  40.                 // cur = cur->next;
  41.  
  42.             }
  43.         }
  44.         else
  45.         {
  46.             if (bigTail == nullptr)
  47.             {
  48.                 bigTail = cur;
  49.                 cur = cur->next; NULL;
  50.                 bigHead->next = bigTail;
  51.             }
  52.             else
  53.             {
  54.                 bigTail->next = cur;
  55.                 cur = cur->next;
  56.  
  57.                 bigTail = bigTail->next;
  58.                 bigTail->next = nullptr;
  59.  
  60.             }
  61.         }
  62.     }
  63.     //小的链表尾连接到大的链表的头
  64.     if (smallTail)
  65.     {
  66.         smallTail->next = bigHead->next;
  67.  
  68.         pHead = smallHead->next;
  69.     }
  70.     else
  71.     {
  72.         pHead = bigHead->next;//smallTail可能为空
  73.     }
  74.     //把2个哨兵位释放
  75.  
  76.     free(smallHead);
  77.     free(bigHead);
  78.  
  79.     return pHead;
  80. }
  81. };
7：链表的回文结构

题目：

思路分析：

大方向： 中间节点 + 链表逆置

1：先找到链表的中间节点 

注意：链表有偶数个节点返回第二个节点

1-> 2-> 2-> 1  对应的中间节点：就是倒数倒数第二个节点

1-> 2-> 3        对应中间节点：就是第二个节点

对于这个代码逻辑的分析，就借助题目3实现即可

链表逆置代码逻辑的分析见题目2

说实话，有的时候 "CV" 大法对于我们程序员来说还是挺香滴

有时候在修修改改，就OK

OJ代码：

  1. class PalindromeList {
  2. public:
  3. struct ListNode* middleNode(struct ListNode* head) //返回链表中间节点
  4. {
  5.     if(head == nullptr)
  6.     return nullptr;
  7.     struct ListNode* fast = head,*slow = head;
  8.     while(fast && fast->next)//逻辑必须是且的关系
  9.     {
  10.         fast = fast->next->next;
  11.         slow = slow->next;
  12.     }
  13.     return slow;
  14. }
  15. struct ListNode* reverseList(struct ListNode* head) //链表逆置
  16. {
  17.  
  18. struct ListNode*  newhead = nullptr,*cur = head;
  19. if(head == nullptr)
  20. return nullptr;
  21. while(cur)
  22. {
  23.     struct ListNode * Next = cur->next;//保留cur的下一个节点，避免找不到
  24.     cur->next = newhead;
  25.     newhead = cur;//新的头结点
  26.      cur = Next;
  27. }
  28. return newhead;
  29. }
  30.     bool chkPalindrome(ListNode* head) {
  31.         // write code here
  32.         // 找到中间节点（偶数个节点：返回第二个）；从中间节点开始进行逆置；以此判断val
  33.        struct ListNode * mid =  middleNode( head);
  34.        struct ListNode * re_mid = reverseList(head);
  35.        while(head)
  36.        {
  37.         if(head->val != re_mid->val)
  38.         {
  39.             return false;
  40.         }
  41.         else {
  42.         head = head->next;
  43.         re_mid =  re_mid->next;
  44.         }
  45.        }
  46.        return true;
  47.     }
  48. };
8：相交链表

 题目：

对于这个OJ题，可能大部分老铁是这样想的：

对这2个链表的每个节点依次进行比较，看链表A 中的 a1是否与链表B中的某个节点相等。搞个循环就拿下了，不知道你是否思考过时间复杂度 ：这个时间复杂度对应的级别O(N^2），在OJ上是跑不过去的

 思路分析：

若是2个链表的尾结点相同，岂不是就相交了

1：注意这里不能比较 节点的val是否相同（此时尾结点的val一样，但是不相交）

2：借用快慢指针的思想：定义fast (指向较长的一个链表)slow(指向链表较短的一个)

3：先让fast走绝对值步 abs(lA-lB)  :注意abs（）是一个库函数

4：在让 fast  和 slow 各自走一步进行判断是否  fast == slow

5：注意一些细节处理：2个链表只有一个节点；当2个链表的长度差很大（换言之就是：slow很快就来到尾结点）

6：找链表尾结点 是 tail ->next == NULL(而不是 tail == NULL)

7:判断链表哪一个长，可以定义一个 longListNode, shortListNode，指针含义顾名思义，这样就避免了每次进循环后的重复判断

 草图见下：

 OJ代码：
  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  2. {
  3.     /*
  4.     快慢指针（拉开距离）：fast（指向较长的链表）slow（指向较短链表）一起走，每次走一步，第一次 fast == slow,就是所求节点
  5.     fast先走 差距步  abs(lA-lB)
  6.     问题不知道那个链表是最长的，定义指针 shortList,longList
  7.     */
  8.     struct ListNode * tailA = headA,*tailB = headB;
  9.    
  10.     int lA = 0,lB = 0;
  11.     while( tailA->next)
  12.     {
  13.         lA++;//注意lA最终比原链表长度少1，但并不影响 abs(lA-lB)
  14.         tailA = tailA->next;
  15.     }
  16.     while(tailB->next)
  17.     {
  18.         lB++;
  19.         tailB = tailB->next;
  20.     }
  21.     int gap = abs(lA-lB);
  22.     if(tailB == tailA)  //相交
  23.     {
  24.         struct ListNode* longList= headA,*shortList = headB;//假设链表A较长
  25.         if(lA >= lB)
  26.         {
  27.         longList = headA;
  28.         shortList = headB;
  29.         }
  30.         else
  31.         {
  32.         longList = headB;
  33.         shortList = headA;
  34.         }
  35.         struct ListNode*fast = longList,*slow = shortList;
  36.         while(gap--)
  37.         {
  38.             fast = fast->next;
  39.         }
  40.         //都只有一个节点，下面循环进不去
  41.         if(fast == slow)
  42.         return fast;
  43.         while(fast && fast->next)
  44.         {
  45.             fast = fast->next;
  46.             if(slow != NULL)  //可能slow先来到尾结点
  47.             slow = slow->next;
  48.             if(fast == slow)
  49.             return fast;
  50.         
  51.         }
  52.     }
  53.     return NULL;//不相交
  54. }

9： 环形链表
题目：

注意此时我们找尾结点是不能解决问题的

对于这种循环链表最大的问题就是不能进行遍历，因为我们永远走不出这个圈（一直死循环） 

 思路分析：

方法：快慢指针

1：fast 和 slow 起始位置都指向头结点

2：fast 每次走 2步  fast = fast ->next ->next ;

     slow 每次走一步 slow = slow ->next ;

3: 当这2个指针相遇即代表此链表成环   即： fast == slow  ；

草图分析：

 比如说：屏幕前的老铁，这正好就是面试题之一，面试官就问原理是啥，

fast 和 slow 一定会相遇吗（fast 走2步，slow 走1步）

fast 走3 \4 \5……又可不可以呢？？？

 相信有不少铁子也会有疑问，为什么呀，原理是啥？？？

证明：

fast 每次走2步， slow 每次走一步，并且这2个指针同时从头结点开始走，那么注定fast指针先进入环，slow 指针后进入环

假设fast 指针追 slow 指针，假设fast 与slow 之间距离为 X 。在速度上 fast 是slow 是2倍，并且 2个指针又是同时从统一起始点出发的，所以当slow 第一次进入环后但没有走完第一圈，fast 肯定会追上 slow

OJ代码：
  1. bool hasCycle(struct ListNode *head)
  2.  {
  3.     while(fast && fast->next)
  4.     {
  5.         fast = fast->next->next;
  6.         slow = slow->next;
  7.         if(fast == slow)
  8.         return true;
  9.     }
  10.     return false;
  11. }
10：环形链表 II

 题目：

对于这个变形题，咱先说思路，一会在进行证明 

思路分析：

方法：一个指针从头结点开始走，一个指针从相遇的节点开始走，当再次相遇即为环的入口节点（即为所求）

 1：快慢指针的思想：当 fast 和 slow 第一次相遇的时候 定义为 meet

2：有一个指针从头结点开始走，一个指针从meet 这个节点开始走，当这2个指针再次相遇即为链表成环的第一个节点

再则里，俺就偷个懒，就不画草图喽

OJ代码： 
  1. struct ListNode *detectCycle(struct ListNode *head) 
  2. {
  3.     /*
  4.     1:判断是否有环：快慢指针
  5.     2：求入环的起始节点->假设相遇的节点是meet，让一个节点从meet开始走，一个从头结点开始走，再次相遇即为所求
  6.     */
  7.     struct ListNode * fast = head,*slow =  head;
  8.     while(fast && fast->next)
  9.     {
  10.         fast = fast->next->next;
  11.         slow = slow->next;
  12.         if( slow == fast)//相遇
  13.         {
  14.             struct ListNode * meet = slow;
  15.             while(meet != head)
  16.             {
  17.                 meet = meet->next;
  18.                 head = head->next;
  19.             }
  20.                 return meet;
  21.             
  22.         }
  23.     }
  24.     return NULL;//没有环
  25. }

 想必有不少老铁会问，原理是啥，能对这个结论进行证明吗？

没问题，接下来3,2,1，上证明

证明：

11：随机链表的复制

题目：

分析： 

当我们看到这个链表的时候，无非就是多了一个 random 指针相较于 单链表而言

我相信有不少老铁是这样思考的：

当节点的random 指针指向非空的时候：第二个节点 直接让 random 指向 节点val 为 7的节点即可

我在这里想说是不行滴当链表LI有2个为7的节点呢，你知道先连哪一个吗？

 有那些铁子说：不如记录一下当前 random 指针指向第几个节点

这样也不是不可以的，但是效率肯定是不太好的 O(N^2)

 我这里有个最优解（仅限于使用C语言）仔细看哟，不要分心，一不小心就出差错了

额外说一下：此时对应时间复杂度的级别是 O（N）

思路分析：

首先：对原来链表进行拷贝，让原节点与拷贝节点建立联系：拷贝的节点尾插到对应节点的后面

其次：控制拷贝节点的random   注意这是解这题的核心

     当random 不为空：  copy -> random = cur ->random->next ;

     当random 为空：copy ->random = NULL ;

最后：让拷贝链表与原链表分开，同时恢复原来链表

定义 3个指针：

copyHead （拷贝链表新的头结点）  copyTail（拷贝链表的尾结点）    curNext

1）把拷贝节点拿下来尾插

对拷贝节点第一次尾插

            copyHead = copyTail = cur -> next ;

            curNext = cur->next->next;

            cur->next = curNext;//恢复原来链表

            cur = curNext;

            copyTail ->next = NULL;

之后对拷贝节点尾插逻辑：

            copyTail->next =cur->next;

            curNext = cur->next->next;

            cur ->next = curNext;//恢复原来链表

            cur = curNext;//迭代

            copyTail = copyTail->next;//尾结点及时更新

            copyTail ->next = NULL;//尾结点及时置空

2）原链表的恢复：让cur -> next = curNext ;

 

 OJ代码：
  1. struct Node* copyRandomList(struct Node* head)
  2.  {
  3.      /*
  4.      1:拷贝节点到原来节点的后面：是源节点与拷贝节点建立联系（实际上：没有任何关系：malloc）
  5.      2：控制拷贝节点的random
  6.      3：让拷贝节点与源节点断开 && 恢复原来链表
  7.      */
  8. 	struct Node* cur = head,*copy = NULL;
  9.     while(cur) //1
  10.     {
  11.         copy = (struct Node*)malloc(sizeof(struct Node));
  12.         if(copy == NULL)
  13.         return NULL;
  14.         //开辟成功，赋值
  15.         copy->val = cur->val;
  16.         copy->next = cur->next;
  17.         struct Node* curNext = cur->next;
  18.         //插入到当前节点后面
  19.         cur->next = copy;
  20.         copy->next = curNext;
  21.         cur = curNext;//迭代
  22.     }
  23.     cur = head;//cur重新赋值
  24.     // copy = cur->next;
  25.     while(cur)//2
  26.     {
  27.          copy = cur->next;//拷贝节点永远在cur 的后面
  28.         if(cur->random == NULL)
  29.         {
  30.              copy->random = NULL;
  31.         }
  32.         else
  33.         {
  34.         copy->random = cur->random->next;
  35.         }
  36.         cur = copy->next;//迭代
  37.     }
  38.     cur = head;//cur重新赋值
  39.     struct Node* copyHead = NULL,*copyTail = NULL,*curNext = NULL;
  40.     while(cur)//3:把拷贝节点取下来尾插
  41.     {
  42.         if(copyTail ==NULL)
  43.         {
  44.             copyHead = copyTail = cur->next;
  45.             curNext = cur->next->next;
  46.             cur->next = curNext;//恢复原来链表
  47.             cur = curNext;
  48.             copyTail ->next = NULL;
  49.         }
  50.         else
  51.         {
  52.             copyTail->next =cur->next;
  53.             curNext = cur->next->next;
  54.             cur ->next = curNext;//恢复原来链表
  55.             cur = curNext;//迭代
  56.             copyTail = copyTail->next;//尾结点及时更新
  57.             copyTail ->next = NULL;//尾结点及时置空
  58.         }
  59.  
  60.     }
  61.     return copyHead;
  62. }
总结： 

对于我这种小白来讲，做链表方面的OJ题，结合画图来说确实是省了不少事情，相比较自己 盲想省去了不少麻烦，在之后就是自己还是要多多练习，注意指针走向，边界的判断

结语：

对于链表这块，需要咱们多多实践，这样才能知不足，而奋进。对于这个快慢指针的应用我们方向是很灵活的，有时候看似题目很难（比如求环形链表入口的第一个节点），采用快慢指针代码量瞬间就变得很精简。其次就是我们在敲代码的时候要注意“数码结合”，画图真的帮我们省了不少问题，ok，话不多说，咱走起，你是懂滴，铁子！

????!!??‧✧̣̥̇‧✦??‧✧̣̥̇‧✦ ??‧✧̣̥̇:Solitary-walk

      ⸝⋆   ━━━┓
     - 个性标签 - ：来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━  ➴ ⷯ

本人座右铭 ：   欲达高峰,必忍其痛;欲戴王冠,必承其重。

??????? 
???自???
???信???
???　???    希望在看完我的此篇博客后可以对你有帮助哟

???????   
???????

目录：
一 ​​​​​​移除链表元素
二：反转一个单链表
三：链表的中间结点
四：链表中倒数第k个结点
五：合并两个有序链表
六：链表分割
七：链表的回文结构
八：相交链表

题目：

九： 环形链表
十：环形链表 II

 十一：

 1： ​​​​​​移除链表元素

思路分析 

这里咱有2中方法可以实现：

方法1：直接在原链表进行删除

总的方向：把等于val 的对应节点直接删除即可，定义三个指针：pre(当前指针的前一个节点),del（要删除的节点),cur（当前节点）

注意细节：

1）当链表第一个节点就需要删除 也就是说  pre == NULL,这时候头结点需要更新

2）正常情况的删除:改变pre指向节点的next ,这时候需要找到删除cur这个节点的前一个节点也就是pre

3非头结点并且也不需要删除：pre依次改变   即 pre = cur

对应草图如下：

OJ代码
  1. struct ListNode* removeElements(struct ListNode* head, int val)
  2.  {
  3.     struct ListNode* cur = head,*pre = NULL,*del = NULL;
  4.     while(cur)
  5.     {
  6.         if(cur->val == val)
  7.         {
  8.             if(pre == NULL)//头结点的删除
  9.             {
  10.                 del = cur;
  11.                 cur = del->next;
  12.               head = cur;//更新头结点
  13.                 free(del);
  14.             }
  15.             else
  16.             {
  17.                 del= cur;
  18.                 cur = del->next;
  19.                 pre->next = cur;
  20.                 free(del);
  21.         
  22.             }
  23.             
  24.         }
  25.         else
  26.         {
  27.             //不需删除
  28.             pre = cur;
  29.             cur = cur->next;
  30.  
  31.         }
  32.     }
  33.     return head;
  34. }

方法2：借助链表尾插函数的思想，把不为 val对应的节点取下来进行尾插

那么问题来了：每次尾插之前都需要先找尾，在时间上就很不占优势n个节点那么对应时间复杂度就是 O(N^2) 

这里我们就需要定义一个tail指针，以此解决此问题

总的方向：不是val的节点拿下来尾插，定义三个指针  tail(尾指针) newhead(新的头结点)cur(指向原链表的当前节点)

注意细节：

1）第一个节点不为val ：执行逻辑是赋值  newhead =tail =  cur; cur = cur->next;  tail->next = NULL;

2) 接下来就是尾插的逻辑，只需要更新尾结点即可  tail ->next = cur; tail = tail->next; cur = cur->next; tail->next = NULL;(注意这2句代码顺序不能颠倒) 

草图见下：

OJ完整代码：
  1. struct ListNode* removeElements(struct ListNode* head, int val)
  2. {    
  3.  //方法2：尾插
  4.     struct ListNode* tail = NULL,*newhead = NULL,*cur = head;
  5.     if(head == NULL)
  6.     return NULL;
  7.     while(cur)
  8.     {
  9.         if(cur->val != val )
  10.         {
  11.             if(newhead == NULL)  //第一次尾插
  12.             {
  13.                 newhead = tail =  cur;
  14.                 cur = cur->next;
  15.                 tail->next = NULL;
  16.             }
  17.             else
  18.             {
  19.                 tail->next = cur;
  20.                 tail = tail->next;//尾结点更新
  21.                 cur = cur->next;
  22.                 tail->next = NULL;//注意以上2句代码位置不能颠倒
  23.             }
  24.         }
  25.         else
  26.         {
  27.             struct ListNode* del  = cur;
  28.             cur = cur->next;
  29.             free(del);
  30.         }
  31.     }
  32.     return newhead;
  33. }

2：反转一个单链表

题目：

 思路分析

对于这题，咱也就是说，不仅仅局限于一种思维，咱格局打开 

方法1：三指针玩法（说白了，就是改变指针走向的问题）

总的方向：定义三个指针 n1 = NULL ; n2 = head; n3 = head->next ;

注意细节：

1）当链表为空的时候 

n3 = head->next; 这不就出现野指针问题了吗

合理的操作应该是：

if(head == NULL)

    return NULL;

2）循环结束条件的判断： 

3）新的头结点的返回

草图见下：

 OJ代码：
  1. struct ListNode* reverseList(struct ListNode* head) {
  2.     // struct ListNode* n1= NULL,*n2 = head,n3 = n2->next;//可能只有一个节点，此时n3是野指针
  3. struct ListNode* n1= NULL,*n2 = head ;
  4. if(head == NULL)//没有节点
  5. return NULL;
  6. if(head->next == NULL) //只有一个节点
  7. return head;
  8.     struct ListNode*n3 = n2->next;
  9.  
  10. while(n2)
  11. {
  12.      n2->next = n1;
  13.     n1 = n2;
  14.     n2 = n3;
  15.     if(n3)
  16.     n3 = n3->next;
  17. }
  18.    return n1; 
  19. }

 方法2：利用头插的思想，定义2个指针  newhead = NULL,cur = head;

  1. struct ListNode* reverseList(struct ListNode* head) {
  2.  
  3. struct ListNode*  newhead = NULL,*cur = head;
  4. if(head == NULL)
  5. return NULL;
  6. while(cur)
  7. {
  8.     struct ListNode * Next = cur->next;//保留cur的下一个节点，避免找不到
  9.     cur->next = newhead;
  10.     newhead = cur;//新的头结点
  11.      cur = Next;
  12. }
  13. return newhead;
  14. }
3：链表的中间结点

 思路分析

 采用快慢指针（fas指针走2步，slow指针走1步）

原理：在速度上fast永远是slow的2倍，所以当fast走到头的时候slow刚好走到链表的一半，slow所指向的节点就是链表的中间节点

 OJ代码：
  1. struct ListNode* middleNode(struct ListNode* head) 
  2. {
  3.     if(head == NULL)
  4.     return NULL;
  5.     struct ListNode* fast = head,*slow = head;
  6.     while(fast && fast->next)//逻辑必须是且的关系
  7.     {
  8.         fast = fast->next->next;
  9.         slow = slow->next;
  10.     }
  11.     return slow;
  12. }
4：链表中倒数第k个结点

题目：

思路讲解： 

方法1：快慢指针（注意这个与上面又有区别只不过思想是一致的） 

1）定义2个指针 fast,slow

2）先让fast指针走k步：利用循环来实现

3）再让2个指针一起走：fast走1步，slow走1步

fast = fast->next->next;

slow = slow->next; 

OJ代码：
  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
  2.     // write code here
  3.     struct ListNode* fast = pListHead,*slow = pListHead,*cur = pListHead;
  4.     if(pListHead ==NULL)
  5.     return NULL;
  6.     int count = 0;
  7.     while(cur)//先求出链表长度
  8.     {
  9.         count++;
  10.         cur = cur->next;
  11.     }
  12.     if(k > count || k == 0)
  13.     return NULL;
  14.     while(k--)
  15.     {
  16.         fast = fast->next; 
  17.     }
  18.  
  19.     while(fast)
  20.     {
  21.         fast = fast->next;
  22.         slow = slow->next;
  23.     }
  24.     return slow;
  25. }
5：合并两个有序链表

题目：

思路分析： 

比较val ，取小的进行尾插

1：定义一个head 指针，一个tail 指针（免去了每一次尾插都需要找尾结点）

2：注意临界条件的判断

草图见下：

OJ代码：
  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
  2.     
  3.     struct ListNode* head = NULL,*tail = NULL;
  4.     if( list1 == NULL&& list2 == NULL)
  5.     return NULL;
  6.     if(list1 == NULL)
  7.     return list2;
  8.     if(list2 == NULL)
  9.     return list1;
  10.     while(list1 && list2 )
  11.     {
  12.         if(list1->val >= list2->val) 
  13.         {
  14.             if(tail == NULL) //第一次尾插
  15.             {
  16.              head = tail= list2;
  17.              list2 = list2->next;
  18.              tail->next = NULL;
  19.             }
  20.             else
  21.             {
  22.              tail->next = list2;
  23.              tail = tail->next;
  24.              if(list2)
  25.               list2 = list2->next;
  26.              tail->next = NULL;//尾结点更新
  27.                 
  28.             }
  29.         }
  30.         else
  31.         {
  32.              if(tail == NULL) //第一次尾插
  33.             {
  34.              head = tail= list1;
  35.              list1 = list1->next;
  36.              tail->next = NULL;
  37.             }
  38.             else
  39.             {
  40.             tail->next = list1;
  41.              tail = tail->next;
  42.              if(list1)
  43.             list1 = list1->next;
  44.              tail->next = NULL;//尾结点更新 
  45.             }
  46.         }
  47.     }
  48.     if(list1 != NULL)
  49.     {
  50.         tail->next = list1;
  51.     }
  52.     if(list2 != NULL)
  53.     {
  54.         tail->next = list2;
  55.  
  56.     }
  57.     return head;
  58. }
6：链表分割

题目：

 思路分析

首先定义2个哨兵位 ： smallHead (指向小于 x值的对应链表）  bigHead(指向大于 x值的对应链表) 避免了空指针的问题

同时方便我们尾插进来找尾结点 定义2个尾指针 smallTail   bigTail

小于 x 进行尾插在 smallTail 

大于 x进行尾插在bigTail

最后把 2个链表进行连接

 草图见下

OJ代码
  1. class Partition {
  2. public:
  3. ListNode* partition(struct ListNode* pHead, int x)
  4. {
  5.     // write code here
  6.     /*
  7.     思路：这两个链表一定要带哨兵位
  8.     小于 x 的尾插到 一个链表
  9.     大于等于 X 的尾插到另一个链表上
  10.     对尾插的节点进行连接
  11.      */
  12.     struct ListNode* smallHead = nullptr, * smallTail = nullptr, * bigHead = nullptr, * bigTail = nullptr;//定义2个哨兵位
  13.     struct ListNode* cur = pHead;
  14.     smallHead = (struct ListNode*)malloc(sizeof(struct ListNode));
  15.     bigHead = (struct ListNode*)malloc(sizeof(struct ListNode));
  16.     smallHead->next = nullptr;
  17.     smallHead->val = -1;
  18.     bigHead->val = -1;
  19.     bigHead->next = nullptr;
  20.  
  21.     while (cur)
  22.     {
  23.         if (cur->val < x)
  24.         {
  25.             if (smallTail == nullptr)
  26.             {
  27.                 smallTail = cur;
  28.                 cur = cur->next;
  29.  
  30.                 smallTail->next = nullptr;
  31.                 smallHead->next = smallTail;
  32.             }
  33.             else
  34.             {
  35.                 smallTail->next = cur;
  36.                 cur = cur->next;
  37.  
  38.                 smallTail = smallTail->next;
  39.                 smallTail->next = nullptr;
  40.                 // cur = cur->next;
  41.  
  42.             }
  43.         }
  44.         else
  45.         {
  46.             if (bigTail == nullptr)
  47.             {
  48.                 bigTail = cur;
  49.                 cur = cur->next; NULL;
  50.                 bigHead->next = bigTail;
  51.             }
  52.             else
  53.             {
  54.                 bigTail->next = cur;
  55.                 cur = cur->next;
  56.  
  57.                 bigTail = bigTail->next;
  58.                 bigTail->next = nullptr;
  59.  
  60.             }
  61.         }
  62.     }
  63.     //小的链表尾连接到大的链表的头
  64.     if (smallTail)
  65.     {
  66.         smallTail->next = bigHead->next;
  67.  
  68.         pHead = smallHead->next;
  69.     }
  70.     else
  71.     {
  72.         pHead = bigHead->next;//smallTail可能为空
  73.     }
  74.     //把2个哨兵位释放
  75.  
  76.     free(smallHead);
  77.     free(bigHead);
  78.  
  79.     return pHead;
  80. }
  81. };
7：链表的回文结构

题目：

思路分析：

大方向： 中间节点 + 链表逆置

1：先找到链表的中间节点 

注意：链表有偶数个节点返回第二个节点

1-> 2-> 2-> 1  对应的中间节点：就是倒数倒数第二个节点

1-> 2-> 3        对应中间节点：就是第二个节点

对于这个代码逻辑的分析，就借助题目3实现即可

链表逆置代码逻辑的分析见题目2

说实话，有的时候 "CV" 大法对于我们程序员来说还是挺香滴

有时候在修修改改，就OK

OJ代码：

  1. class PalindromeList {
  2. public:
  3. struct ListNode* middleNode(struct ListNode* head) //返回链表中间节点
  4. {
  5.     if(head == nullptr)
  6.     return nullptr;
  7.     struct ListNode* fast = head,*slow = head;
  8.     while(fast && fast->next)//逻辑必须是且的关系
  9.     {
  10.         fast = fast->next->next;
  11.         slow = slow->next;
  12.     }
  13.     return slow;
  14. }
  15. struct ListNode* reverseList(struct ListNode* head) //链表逆置
  16. {
  17.  
  18. struct ListNode*  newhead = nullptr,*cur = head;
  19. if(head == nullptr)
  20. return nullptr;
  21. while(cur)
  22. {
  23.     struct ListNode * Next = cur->next;//保留cur的下一个节点，避免找不到
  24.     cur->next = newhead;
  25.     newhead = cur;//新的头结点
  26.      cur = Next;
  27. }
  28. return newhead;
  29. }
  30.     bool chkPalindrome(ListNode* head) {
  31.         // write code here
  32.         // 找到中间节点（偶数个节点：返回第二个）；从中间节点开始进行逆置；以此判断val
  33.        struct ListNode * mid =  middleNode( head);
  34.        struct ListNode * re_mid = reverseList(head);
  35.        while(head)
  36.        {
  37.         if(head->val != re_mid->val)
  38.         {
  39.             return false;
  40.         }
  41.         else {
  42.         head = head->next;
  43.         re_mid =  re_mid->next;
  44.         }
  45.        }
  46.        return true;
  47.     }
  48. };
8：相交链表

 题目：

对于这个OJ题，可能大部分老铁是这样想的：

对这2个链表的每个节点依次进行比较，看链表A 中的 a1是否与链表B中的某个节点相等。搞个循环就拿下了，不知道你是否思考过时间复杂度 ：这个时间复杂度对应的级别O(N^2），在OJ上是跑不过去的

 思路分析：

若是2个链表的尾结点相同，岂不是就相交了

1：注意这里不能比较 节点的val是否相同（此时尾结点的val一样，但是不相交）

2：借用快慢指针的思想：定义fast (指向较长的一个链表)slow(指向链表较短的一个)

3：先让fast走绝对值步 abs(lA-lB)  :注意abs（）是一个库函数

4：在让 fast  和 slow 各自走一步进行判断是否  fast == slow

5：注意一些细节处理：2个链表只有一个节点；当2个链表的长度差很大（换言之就是：slow很快就来到尾结点）

6：找链表尾结点 是 tail ->next == NULL(而不是 tail == NULL)

7:判断链表哪一个长，可以定义一个 longListNode, shortListNode，指针含义顾名思义，这样就避免了每次进循环后的重复判断

 草图见下：

 OJ代码：
  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  2. {
  3.     /*
  4.     快慢指针（拉开距离）：fast（指向较长的链表）slow（指向较短链表）一起走，每次走一步，第一次 fast == slow,就是所求节点
  5.     fast先走 差距步  abs(lA-lB)
  6.     问题不知道那个链表是最长的，定义指针 shortList,longList
  7.     */
  8.     struct ListNode * tailA = headA,*tailB = headB;
  9.    
  10.     int lA = 0,lB = 0;
  11.     while( tailA->next)
  12.     {
  13.         lA++;//注意lA最终比原链表长度少1，但并不影响 abs(lA-lB)
  14.         tailA = tailA->next;
  15.     }
  16.     while(tailB->next)
  17.     {
  18.         lB++;
  19.         tailB = tailB->next;
  20.     }
  21.     int gap = abs(lA-lB);
  22.     if(tailB == tailA)  //相交
  23.     {
  24.         struct ListNode* longList= headA,*shortList = headB;//假设链表A较长
  25.         if(lA >= lB)
  26.         {
  27.         longList = headA;
  28.         shortList = headB;
  29.         }
  30.         else
  31.         {
  32.         longList = headB;
  33.         shortList = headA;
  34.         }
  35.         struct ListNode*fast = longList,*slow = shortList;
  36.         while(gap--)
  37.         {
  38.             fast = fast->next;
  39.         }
  40.         //都只有一个节点，下面循环进不去
  41.         if(fast == slow)
  42.         return fast;
  43.         while(fast && fast->next)
  44.         {
  45.             fast = fast->next;
  46.             if(slow != NULL)  //可能slow先来到尾结点
  47.             slow = slow->next;
  48.             if(fast == slow)
  49.             return fast;
  50.         
  51.         }
  52.     }
  53.     return NULL;//不相交
  54. }

9： 环形链表
题目：

注意此时我们找尾结点是不能解决问题的

对于这种循环链表最大的问题就是不能进行遍历，因为我们永远走不出这个圈（一直死循环） 

 思路分析：

方法：快慢指针

1：fast 和 slow 起始位置都指向头结点

2：fast 每次走 2步  fast = fast ->next ->next ;

     slow 每次走一步 slow = slow ->next ;

3: 当这2个指针相遇即代表此链表成环   即： fast == slow  ；

草图分析：

 比如说：屏幕前的老铁，这正好就是面试题之一，面试官就问原理是啥，

fast 和 slow 一定会相遇吗（fast 走2步，slow 走1步）

fast 走3 \4 \5……又可不可以呢？？？

 相信有不少铁子也会有疑问，为什么呀，原理是啥？？？

证明：

fast 每次走2步， slow 每次走一步，并且这2个指针同时从头结点开始走，那么注定fast指针先进入环，slow 指针后进入环

假设fast 指针追 slow 指针，假设fast 与slow 之间距离为 X 。在速度上 fast 是slow 是2倍，并且 2个指针又是同时从统一起始点出发的，所以当slow 第一次进入环后但没有走完第一圈，fast 肯定会追上 slow

OJ代码：
  1. bool hasCycle(struct ListNode *head)
  2.  {
  3.     while(fast && fast->next)
  4.     {
  5.         fast = fast->next->next;
  6.         slow = slow->next;
  7.         if(fast == slow)
  8.         return true;
  9.     }
  10.     return false;
  11. }
10：环形链表 II

 题目：

对于这个变形题，咱先说思路，一会在进行证明 

思路分析：

方法：一个指针从头结点开始走，一个指针从相遇的节点开始走，当再次相遇即为环的入口节点（即为所求）

 1：快慢指针的思想：当 fast 和 slow 第一次相遇的时候 定义为 meet

2：有一个指针从头结点开始走，一个指针从meet 这个节点开始走，当这2个指针再次相遇即为链表成环的第一个节点

再则里，俺就偷个懒，就不画草图喽

OJ代码： 
  1. struct ListNode *detectCycle(struct ListNode *head) 
  2. {
  3.     /*
  4.     1:判断是否有环：快慢指针
  5.     2：求入环的起始节点->假设相遇的节点是meet，让一个节点从meet开始走，一个从头结点开始走，再次相遇即为所求
  6.     */
  7.     struct ListNode * fast = head,*slow =  head;
  8.     while(fast && fast->next)
  9.     {
  10.         fast = fast->next->next;
  11.         slow = slow->next;
  12.         if( slow == fast)//相遇
  13.         {
  14.             struct ListNode * meet = slow;
  15.             while(meet != head)
  16.             {
  17.                 meet = meet->next;
  18.                 head = head->next;
  19.             }
  20.                 return meet;
  21.             
  22.         }
  23.     }
  24.     return NULL;//没有环
  25. }

 想必有不少老铁会问，原理是啥，能对这个结论进行证明吗？

没问题，接下来3,2,1，上证明

证明：

11：随机链表的复制

题目：

分析： 

当我们看到这个链表的时候，无非就是多了一个 random 指针相较于 单链表而言

我相信有不少老铁是这样思考的：

当节点的random 指针指向非空的时候：第二个节点 直接让 random 指向 节点val 为 7的节点即可

我在这里想说是不行滴当链表LI有2个为7的节点呢，你知道先连哪一个吗？

 有那些铁子说：不如记录一下当前 random 指针指向第几个节点

这样也不是不可以的，但是效率肯定是不太好的 O(N^2)

 我这里有个最优解（仅限于使用C语言）仔细看哟，不要分心，一不小心就出差错了

额外说一下：此时对应时间复杂度的级别是 O（N）

思路分析：

首先：对原来链表进行拷贝，让原节点与拷贝节点建立联系：拷贝的节点尾插到对应节点的后面

其次：控制拷贝节点的random   注意这是解这题的核心

     当random 不为空：  copy -> random = cur ->random->next ;

     当random 为空：copy ->random = NULL ;

最后：让拷贝链表与原链表分开，同时恢复原来链表

定义 3个指针：

copyHead （拷贝链表新的头结点）  copyTail（拷贝链表的尾结点）    curNext

1）把拷贝节点拿下来尾插

对拷贝节点第一次尾插

            copyHead = copyTail = cur -> next ;

            curNext = cur->next->next;

            cur->next = curNext;//恢复原来链表

            cur = curNext;

            copyTail ->next = NULL;

之后对拷贝节点尾插逻辑：

            copyTail->next =cur->next;

            curNext = cur->next->next;

            cur ->next = curNext;//恢复原来链表

            cur = curNext;//迭代

            copyTail = copyTail->next;//尾结点及时更新

            copyTail ->next = NULL;//尾结点及时置空

2）原链表的恢复：让cur -> next = curNext ;

 

 OJ代码：
  1. struct Node* copyRandomList(struct Node* head)
  2.  {
  3.      /*
  4.      1:拷贝节点到原来节点的后面：是源节点与拷贝节点建立联系（实际上：没有任何关系：malloc）
  5.      2：控制拷贝节点的random
  6.      3：让拷贝节点与源节点断开 && 恢复原来链表
  7.      */
  8. 	struct Node* cur = head,*copy = NULL;
  9.     while(cur) //1
  10.     {
  11.         copy = (struct Node*)malloc(sizeof(struct Node));
  12.         if(copy == NULL)
  13.         return NULL;
  14.         //开辟成功，赋值
  15.         copy->val = cur->val;
  16.         copy->next = cur->next;
  17.         struct Node* curNext = cur->next;
  18.         //插入到当前节点后面
  19.         cur->next = copy;
  20.         copy->next = curNext;
  21.         cur = curNext;//迭代
  22.     }
  23.     cur = head;//cur重新赋值
  24.     // copy = cur->next;
  25.     while(cur)//2
  26.     {
  27.          copy = cur->next;//拷贝节点永远在cur 的后面
  28.         if(cur->random == NULL)
  29.         {
  30.              copy->random = NULL;
  31.         }
  32.         else
  33.         {
  34.         copy->random = cur->random->next;
  35.         }
  36.         cur = copy->next;//迭代
  37.     }
  38.     cur = head;//cur重新赋值
  39.     struct Node* copyHead = NULL,*copyTail = NULL,*curNext = NULL;
  40.     while(cur)//3:把拷贝节点取下来尾插
  41.     {
  42.         if(copyTail ==NULL)
  43.         {
  44.             copyHead = copyTail = cur->next;
  45.             curNext = cur->next->next;
  46.             cur->next = curNext;//恢复原来链表
  47.             cur = curNext;
  48.             copyTail ->next = NULL;
  49.         }
  50.         else
  51.         {
  52.             copyTail->next =cur->next;
  53.             curNext = cur->next->next;
  54.             cur ->next = curNext;//恢复原来链表
  55.             cur = curNext;//迭代
  56.             copyTail = copyTail->next;//尾结点及时更新
  57.             copyTail ->next = NULL;//尾结点及时置空
  58.         }
  59.  
  60.     }
  61.     return copyHead;
  62. }
总结： 

对于我这种小白来讲，做链表方面的OJ题，结合画图来说确实是省了不少事情，相比较自己 盲想省去了不少麻烦，在之后就是自己还是要多多练习，注意指针走向，边界的判断

结语：

对于链表这块，需要咱们多多实践，这样才能知不足，而奋进。对于这个快慢指针的应用我们方向是很灵活的，有时候看似题目很难（比如求环形链表入口的第一个节点），采用快慢指针代码量瞬间就变得很精简。其次就是我们在敲代码的时候要注意“数码结合”，画图真的帮我们省了不少问题，ok，话不多说，咱走起，你是懂滴，铁子！

注：本文转载自blog.csdn.net的Solitary_walk的文章"https://blog.csdn.net/X_do_myself/article/details/136005048"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！