首页 > 代码库 > Linked List Cycle
Linked List Cycle
https://oj.leetcode.com/problems/linked-list-cycle/
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next == null){ return false; } while(head.next != null){ if(head.next == head){ return true; } ListNode temp = head.next; head.next = head.next.next; temp.next = head; } return false; }}
解题思路：
如果head节点的next不指向当前节点，则删去下个节点（当前节点的next指向下一个节点的next），直到找到return true。否则下个节点null了，就证明到底了，没有回环，返回false。head节点永远不动，其实就是删去后面的。
这么做有两个问题，首先值考虑了1，2，3，1的情况，没考虑回环可能在中间，即1，2，3，4，2。这样就会死循环了，因为1！=2，循环永远不会停止。其次，会改变原来的list结构，
第一个问题，下一个节点的next不指向当前节点的话，不要删除，将其next指向head节点，这样后面如果有回环，无论他指向谁，由于前面都已经指向head了，最后总能判断出来。
第二个问题，可以用快慢跑步的方法。从head开始，fast指针一次走两步，slow一次走一步。如果有回环，他们一定会有一天指向同一个节点，如果没有，fast到null就结束了。
Linked List Cycle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。