Linked List Cycle
今天是一道有關(guān)鏈表的題目欺嗤，來自LeetCode参萄，難度為Medium，Acceptance為36.6%煎饼。
題目如下
Given a linked list, determine if it has a cycle in it.
Example
Given-21->10->4->5, tail connects to node index 1, returntrue
Challenge
Follow up:
Can you solve it without using extra space?
解題思路及代碼見閱讀原文
回復(fù)0000查看更多題目
解題思路
首先讹挎，該題雖然是Medium，但是通過率達(dá)到36.6%腺占，可見很多同學(xué)都見過這道題淤袜，所有我也不會過多解釋。
那么衰伯，思路是怎樣的呢。其實(shí)很簡單积蔚，見過該題的同學(xué)肯定也知道：因?yàn)檫@里是一個單項(xiàng)鏈表意鲸，如果沒有環(huán)，那么最后一個元素的next必定指向null尽爆；所以我們可以用一個快指針怎顾、一個慢指針，快指針一次走兩步漱贱，慢指針一次走一步槐雾，這樣如果快指針最后指向了null,那么肯定是沒有環(huán)；如果快指針最后追上了慢指針即有環(huán)幅狮。
最后募强，就是考慮循環(huán)的終止條件株灸，很顯然即快指針是否指向null。
代碼如下
java版
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
public boolean hasCycle(ListNode head) {
// write your code here
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
return true;
}
return false;
}
}
關(guān)注我
該公眾號會每天推送常見面試題擎值，包括解題思路是代碼慌烧，希望對找工作的同學(xué)有所幫助
image
