一、循环链表

题目描述

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){ return false; } ListNode p=new ListNode(0); p=head; int u=-987123; while(p.val!=u&&p.next!=null){ p.val=u; p=p.next; } if(p.val==u){ return true; } else{ return false; } } }

思路二

• 当然标准的是应该用两个指针来“追赶”，前提是这两个指针走的速度不一样，一前一后如果相遇了则说明有回路。

代码二

/** * 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){ return false; } ListNode p=head; ListNode q=head.next; while(p!=q&&q!=null&&p!=null){ q=q.next; if(q!=null){ q=q.next; } p=p.next; } if(p==q&&p!=null){ return true; } else{ return false; } } }

优化过的代码：

/** * 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){ return false; } ListNode fastNode=head; ListNode lowNode=head; while(fastNode!=null&&fastNode.next!=null){ fastNode=fastNode.next.next; lowNode=lowNode.next; if(fastNode==lowNode){ return true; } } return false; } }

今天有场考试，到七点半才结束，就刷这么多了。