一、循环链表
题目描述
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;
}
}
今天有场考试,到七点半才结束,就刷这么多了。