141. Linked List Cycle

مسئله:

با فرض بر اینکه head سَر یک لیست پیوندی است، مشخص کنید که آیا این لیست پیوندی دارای دور (حلقه) است یا خیر.

اگر گره‌ای در لیست پیوندی وجود داشته باشد که بتوان با دنبال کردن مداوم اشاره گر بعدی (next) دوباره به آن رسید، در آن صورت یک دور در لیست پيوندی وجود دارد. به طور داخلی، از pos برای نشان دادن اندیس گره‌ای که اشاره گر next انتهایی (tail) به آن متصل است استفاده می‌شود. توجه داشته باشید که pos به عنوان پارامتر منتقل نمی‌شود.

در صورتی که لیست پيوندی دارای دور باشد مقدار True و در غیر این صورت مقدار False برگردانید.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
توضیح: یک دور در لیست پيوندی وجود دارد، جایی که انتها به اولین گره (با اندیس 0) متصل می شود.

Example 2:

Input: head = [1,2], pos = 0
Output: true
توضیح: یک دور در لیست پیوندی وجود دارد، جایی که انتهای به گره صفرم (0th node) متصل می شود.

Example 3:

Input: head = [1], pos = -1
Output: false
توضیح: هیچ دور (حلقه‌ای) در لیست پیوندی وجود ندارد.

قیدها:

‏- تعداد گره‌های موجود در لیست پیوندی بین 0 تا 104 است.‏ ‏

- مقدار ورودی بین:

-10^5 <= Node.val <= 10^5

‏‏- مقدار pos برابر با ۱- یا یک مقدار index معتبر در لیست پیوندی است.

پیگیری: آیا می توانید این مسئله را با حافظه O(1) (به عنوان مثال ثابت) حل کنید؟

راه حل ۱: جدول Hash

ما می‌توانیم لیست پیوندی را پیمایش کنیم و از یک جدول Hash برای ثبت هر گره استفاده کنیم. هنگامی که یک گره برای بار دوم ظاهر می شود، نشان دهنده وجود یک دور (حلقه) است و ما مستقیماً مقدار true را برمی‌گردانیم. در غیر این صورت، زمانی که پیمایش لیست پیوندی به پایان می رسد، مقدار false را برمی گردانیم.

پیچیدگی زمانی O(n) و پیچیدگی فضایی O(n) است، که در آن n تعداد گره های موجود در لیست پیوندی است.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
 s := map[*ListNode]bool{}
 for ; head != nil; head = head.Next {
  if s[head] {
   return true
  }
  s[head] = true
 }
 return false
}

راه حل ۲: اشاره‌گرهای سریع و کند

ما دو اشاره‌گر تعریف می کنیم، fast و slow که هر دو در ابتدا به head لیست اشاره می‌کنند. اشاره‌گر fast هر بار حرکت، دو گام به جلو برمی‌دارد و اشاره‌گر slow در هر بار حرکت، یک گام به جلو برمی‌دارد. این حرکت به صورت یک حلقه‌ی پیوسته انجام می‌شود. هنگامی که اشاره‌گرهای fast و slow با هم برخورد می‌کنند، نشان‌دهنده وجود یک دور (حلقه) در لیست پیوندی است. اگر حلقه بدون برخورد اشاره‌گرها به پایان برسد، نشان می‌دهد که هیچ دور (حلقه‌ای) در لیست پیوندی وجود ندارد.

پیچیدگی زمانی O(n) و پیچیدگی فضایی O(1) است، که در آن n تعداد گره های موجود در لیست پیوندی است.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
 slow, fast := head, head
 for fast != nil && fast.Next != nil {
  slow, fast = slow.Next, fast.Next.Next
  if slow == fast {
   return true
  }
 }
 return false
}