程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Linked List Cycle 2

leetcode筆記:Linked List Cycle 2

編輯:關於C++

一. 題目描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up: Can you solve it without using extra space?

二. 題目分析

在Linked List Cycle題目中,使用了兩個指針fast與slow檢查鏈表是否有環,該題在此基礎上,要求給出鏈表中環的入口位置,同樣需要注意空間復雜度。為了方便解釋,以下給出一個有環鏈表:

這裡寫圖片描述

其中,設鏈表頭節點到環入口處的距離為X,環長度為Y,使用fastslow兩個指針,fast指針一次前進兩步,slow指針一次前進一步,則他們最終會在環中的K節點處相遇,設此時fast指針已經在環中走過了m圈,slow指針在環中走過n圈,則有:

fast所走的路程:2*t = X+m*Y+K<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxjb2RlPnNsb3c8L2NvZGU+y/nX37XEwrezzKO6PGNvZGU+dCA9IFgrbipZK0s8L2NvZGU+PC9wPg0KPHA+08nV4sG9uPa3vbPMv8m1w7W9o7o8L3A+DQo8cD48Y29kZT4yWCArIDJuKlkgKyAySyA9IFggKyBtKlkgKyBLPC9jb2RlPjwvcD4NCjxwPr340ruyvbXDtb2juiA8Y29kZT5YK0sgPSAobS0ybilZPC9jb2RlPjwvcD4NCjxwPjxzdHJvbmc+tNM8Y29kZT5YK0sgPSAobS0ybilZPC9jb2RlPiC/ybeiz9ajrFi1xLOktsi808nPS7XEs6S2yLXI09q7t7OktshZtcTV+8r9sbajoTwvc3Ryb25nPtLytMu/ybXDtb3Su7j2veHC26OsvLS1sTxjb2RlPmZhc3Q8L2NvZGU+0+s8Y29kZT5zbG93PC9jb2RlPs/g0/bKsaOsv8nKudPDtdrI/bj21rjV6zxjb2RlPkxpc3ROb2RlKiBjeWNsZVN0YXJ0ID0gaGVhZDs8L2NvZGU+o6y008G0se3Nt73atePN+cew19+jrDxjb2RlPnNsb3c8L2NvZGU+1rjV69KyvMzQ+M35x7DX36Os1rG1vTxjb2RlPnNsb3c8L2NvZGU+0+s8Y29kZT5jeWNsZVN0YXJ0PC9jb2RlPs/g0/ajrLjDzrvWw77NysfBtLHt1tC7t7XEyOu/2rSmoaM8L3A+DQo8cD48c3Ryb25nPsj9LiDKvsD9tPrC6zwvc3Ryb25nPjwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> #include using namespace std; struct ListNode { int value; ListNode* next; ListNode(int x) :value(x), next(NULL){} }; class Solution { public: ListNode *detectCycle(ListNode *head) { if (head == NULL || head->next == NULL || head->next->next == NULL) return head; ListNode* fast = head; ListNode* slow = head; while (fast->next->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { ListNode* cycleStart = head; while (slow != cycleStart) { slow = slow->next; cycleStart = cycleStart->next; } return cycleStart; } } return NULL; } };

一個有環鏈表,環從第二個節點開始:

這裡寫圖片描述

四. 小結

解答與鏈表有關的題目時,要多畫圖,找規律,否則容易遇到各種邊界問題。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved