当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.141.Linked List Cycle

LeetCode.141.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?


解题过程

这道题三年前准备校招面试的时候做过,面试过程中也被问到过不止一次,印象很深刻,知道是用双指针做,但具体怎么做有点儿模糊了。昨晚睡前看了这道题后躺床上就想,由于知道用双指针,思维被固话了,使劲想怎么往双指针上靠,不一会儿想出来了:一快一慢两个指针,快的步长为2,慢的步长为1,如果两个指针重合了就说明有环

说实话,如果从来没做过这道题,从头开始想,可能根本不知道怎么做,但永远不会有这种机会了,这道题想忘都忘不了。

代码写起来也很简单,注意快指针往前走时要判断next是否为null,否则会报空指针错误,一次AC:

package _141_LinkedListCycle;

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
    }
}

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(slow!=null && fast!=null){
            slow = slow.next;
            if(fast.next !=null)
                fast = fast.next.next;
            else
                return false;
            if(slow==fast)
                return true;
        }
        return false;
    }
}

public class LinkedListCycle {
    public static void main(String[] args){
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        head.next = head;
        second.next = third;
        third.next = head;
        Solution solution = new Solution();
        System.out.println(solution.hasCycle(head));
    }
}

在讨论区看到两个比较奇葩的方法,一个是把遍历过的结点值都设为Integer.MIN_VALUE,虽然笨但也可行:

public class Solution {
    public boolean hasCycle(ListNode head) {
        while(head != null && head.next != null) {
            if(head.val == Integer.MIN_VALUE)
                return true;
            head.val = Integer.MIN_VALUE;
            head = head.next;
        }
        return false;
    }
}

还有一个是用递归,把遍历过的结点的next指针都指向head,如果某次遇到指向head的结点则说明有环:

class HasCycleInLinkedList{
  public boolean hasCycle(ListNode head){
      if(head == null || head.next == null) return false;
      if(head.next == head) return true;
      ListNode nextNode = head.next; 
      head.next = head;
      boolean isCycle = hasCycle(nextNode);
      return isCycle;
  }
}

不过这两种方法都会修改链表结构,如果题目再加一个不允许修改链表的条件就不能用了。


GitHub代码


上一篇 LeetCode.142.Linked List Cycle II

下一篇 LeetCode.371.Sum of Two Integers

阅读
556
阅读预计2分钟
创建日期 2018-01-30
修改日期 2018-01-31
类别
百度推荐