【链表】环形链表

环形链表

本文只是节选公众号的中的一篇，我的公众号每日都会更新，欢迎参观 公众号算法每日一更

❝

leetcode链接：https://leetcode.cn/problems/linked-list-cycle-ii/

题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

❞

• 错误解法：两层循环

  ❝

  如果环在后面，就会一直循环下去

  ❞

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    typedef struct ListNode ListNode;
    ListNode *fakehead = (ListNode*)malloc(sizeof(ListNode));
    fakehead -> next = head;
    ListNode *cur, *temp;
    cur = fakehead;
    temp = cur -> next;
    while(cur != NULL && temp != NULL){
        do
            temp = temp -> next;
        while(cur -> next != temp && temp != NULL);
        if(cur -> next == temp)
            return temp;
        cur = cur -> next;
        temp = cur -> next;
    }
    return NULL;
}

• 正确解法：快慢指针

  ❝

  如果slow每次走一步，fast每次走两步，有环则一定相遇

  ❞

  // 难点1：判断环 -> 快慢指针
  // 难点2：找环的入口https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     struct ListNode *next;
   * };
   */
  struct ListNode *detectCycle(struct ListNode *head) {
      typedef struct ListNode ListNode;
      ListNode *fast, *slow;
      fast = slow = head;
      while(fast && fast -> next){
          slow = slow -> next;
          fast = fast -> next; 
          if(fast -> next != slow)
              fast = fast -> next;
          else{ // 找到环
              ListNode *index1, *index2;
              index1 = head, index2 = slow;
              while(index1 != index2){
                  index1 = index1 -> next;
                  index2 = index2 -> next;
              }
              return index1;
          }
      }
      return NULL;
  }
  ```