LeetCode 75 Level 1 - Day 4 Linked List

142. Linked List Cycle II

• 題目連結
• 難易度：Medium

題目敘述

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.

預設函數

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

題目限制

1. The number of the nodes in the list is in the .
2. 
3. pos is -1 or a valid index in the linked-list.

解題過程及程式碼

本題是linked list的第4題，也是這個系列第一次碰到Medium難度，題目給一個linked list，需要檢查list中是否有閉環存在 (如下圖)，若有找到閉環則回傳該閉環最開始重複節點的指標 (如下圖②節點的記憶體位置)，若不存在閉環也就是list是有終點的話則回傳NULL。

• 一開始想到的方法是用一個[10000]的陣列來儲存所有走過的節點指標，出現有重複的指標就表示list存在有閉環

  struct ListNode *detectCycle(struct ListNode *head) {
      struct ListNode *ptr_array[10000] = {0};
      struct ListNode *ptr;
      int index = 0;
      int flag = 0;
  
      if (head == NULL) {
          return NULL;
      }
  
      ptr = head;
  
      while (ptr->next != NULL) {
          ptr_array[index] = ptr;
          if (isInArray(ptr_array, ptr->next, index)) {  // 檢查是否已存在陣列裡
              return  ptr->next;
          }
          index++;
          ptr = ptr->next;
      }
      return NULL;
  }
  
  int isInArray(struct ListNode** array, struct ListNode *node, int num) {
      int i;
  
      for (i=0; i<num; i++) {
          if (array[i] == node) {
              return 1;
          }
      }
      return 0;
  }
  
  

• 後來覺得時間複雜度不太理想，程式需要不停的去查詢陣列，參考網路上的做法，發現可以利用雙指標的方法

  • 詳細原理推薦參考這篇寫得很好[Day 16] 演算法刷題 LeetCode 142. Linked List Cycle II (Medium)

• 雙指標程式碼，時間從240ms降到11ms，效果驚人!

  struct ListNode *detectCycle(struct ListNode *head) {
      struct ListNode *ptr1, *ptr2, *ptr3;
  
      if (head == NULL) {
          return NULL;
      }
  
      ptr1 = head;
      ptr2 = head;
  
      while ((ptr2 != NULL) && (ptr2->next != NULL)) {
          ptr1 = ptr1->next;
          ptr2 = ptr2->next->next;
  
          if (ptr1 == ptr2) {
              ptr3 = head;
              while (ptr1 != ptr3) {
                  ptr1 = ptr1->next;
                  ptr3 = ptr3->next;
              }
              return ptr1;
          }
      }
  
      return NULL;
  }
  

今天就到這裡，謝謝大家!