• 链表快慢指针合集(力扣)


    876. 链表的中间结点

    代码

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
    public:
        ListNode* middleNode(ListNode* head) {
             ListNode * slow = head, * fast = head;
            while(fast && fast -> next){
                slow = slow->next;
                fast = fast->next->next;
            }//找中间节点
            return slow;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    876. 链表的中间结点

    代码

      141. 环形链表

      代码

      /**
       * Definition for singly-linked list.
       * struct ListNode {
       *     int val;
       *     ListNode *next;
       *     ListNode(int x) : val(x), next(NULL) {}
       * };
       */
      class Solution {
      public:
          bool hasCycle(ListNode *head) {
              ListNode * slow = head, * fast = head;
              while(fast && fast -> next){
                  slow = slow->next;
                  fast = fast -> next -> next;
                  if(slow == fast) return true;
              }
              return false;
      
          }
      };
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21

      142. 环形链表 II

      代码

      /**
       * Definition for singly-linked list.
       * struct ListNode {
       *     int val;
       *     ListNode *next;
       *     ListNode(int x) : val(x), next(NULL) {}
       * };
       */
      class Solution {
      public:
          ListNode *detectCycle(ListNode *head) {
              ListNode * slow = head, *fast = head;
              while(fast && fast -> next){
                  slow = slow -> next;
                  fast = fast -> next -> next;
                  if(slow == fast){
                      while(head != slow){
                          head = head->next;
                          slow = slow -> next;
                      }
                      return slow;
                  }
              }
              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

      LCR 026. 重排链表

      代码

      /**
       * Definition for singly-linked list.
       * struct ListNode {
       *     int val;
       *     ListNode *next;
       *     ListNode() : val(0), next(nullptr) {}
       *     ListNode(int x) : val(x), next(nullptr) {}
       *     ListNode(int x, ListNode *next) : val(x), next(next) {}
       * };
       */
      class Solution {
      public:
          void reorderList(ListNode* head) {
              ListNode * slow = head, * fast = head;
              while(fast && fast -> next){
                  slow = slow->next;
                  fast = fast->next->next;
              }//找中间节点
              ListNode * prev = nullptr, * cur = slow;
              while(cur){
                  ListNode * tp = cur -> next;
                  cur -> next = prev;
                  prev = cur;
                  cur = tp;
              }//反转后半段链表
              ListNode * head2 = prev, *head1 = head;
              while(head2 -> next){
                  ListNode * tp1 = head1->next, * tp2 = head2 -> next;
                  head2->next = head1->next;
                  head1->next = head2;
                  head1 = tp1;
                  head2 = tp2;
              }//令交错指向,最终head2的下一个为空结束
          }
      };
      
      • 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
    • 相关阅读:
      数据持久化第七课-URL重写与Ajax
      java 系统的一些基础知识
      GBase 8c V3.0.0数据类型——HLL函数和操作符(日志函数)
      互融云贷款中介平台搭建,助力企业实现数字化智能办公
      OpenCV+特征检测
      Vivado 综合后工程
      uniapp 常见的问题以及解决办法
      Tensorflow图像识别 Tensorflow手写体识别(二)
      并发性,时间和相对性(1)-确定前后关系
      TCP的三次握手、四次挥手!就像打电话一样简单!
    • 原文地址:https://blog.csdn.net/m0_51305283/article/details/136772124