Leetcode笔记 #141. Linked List Cycle

Problem
Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Author's note
I’m not sure how pos is related to the problem itself but it teaches us how to represent a cycle in future coding practice.

Idea 1: Hash Table
The idea is very clear. We check every node and see we have seen this node before, if not, save into the hash table and check the next node.

HashSet vs. HashMap
Why do we choose a HashSet instead of a HashMap?

• HashSet is a set, e.g. {1, 2, 3, 4, 5},
• HashMap is a key -> value pair map, e.g. {a -> 1, b -> 2, c -> 2, d -> 1}
  

Since we only need to save one node (actually it’s the address of the node) instead of a key-value pair, we’d like to choose a HashSet instead of a HashMap.

HashSet
There are 3 commands that we should know to solve this problem.

• Create: Set<ListNode> seen = new HashSet<ListNode>();
• Check if X is contained in a HashSet: seen.contains(X) // true or false
• Add X to a HashSet: seen.add(X)
  

Code

1. // Hash Table
   
2. public class Solution {
   
3.     public boolean hasCycle(ListNode head) {
   
4.         // Create a hashtable
   
5.         Set<ListNode> seen = new HashSet<ListNode>();
   
6.         
   
7.         // We check every node and see we have seen this node before,
   
8.         // if not, save into the hash table and check the next node.
   
9.         while (head != null) {
   
10.             if (seen.contains(head)) return true;
    
11.             else seen.add(head);
    
12.             head = head.next;
    
13.         }
    
14.         return false;
    
15.     }
    
16. }

复制代码

Idea 2: 2 pointers
We can use 2 pointers with different speed and check if they meet. So we need to design their speed careful so that they don’t miss each other, like this:

• Creating a pointer slow who walks 1 step each time
• Creating a pointer fast who walks 2 steps each time.
  

In this way they will finally meet. “Leetcode - solutions” explains this part very well.


Code

1. // 2 pointers
   
2. public class Solution {
   
3.     public boolean hasCycle(ListNode head) {
   
4.         // Since we're using the value of head and head.next to initialize pointers,
   
5.         // we need to make sure that they are not null.
   
6.         if (head == null || head.next == null) return false;
   
7.         
   
8.         // Set up 2 pointers
   
9.         ListNode slow = head;
   
10.         ListNode fast = head.next;
    
11.         while (slow != fast) {
    
12.             if (fast == null || slow == null) return false;
    
13.             fast = fast.next.next;  // fast.next.next is different with head.next.next in #206(recursive) since here fast.next.next doesn't change it's value while head.next.next in #206(recursive) is assigned to a new value so that it's pointing back.
    
14.             slow = slow.next;
    
15.         }
    
16.         
    
17.         // Only return true when 2 pointers are the same
    
18.         return true;
    
19.     }
    
20. }

复制代码

方法一里面第10行和11行可以写得更compact一些，

1. if (!seen.add(head)) return true;

复制代码

快慢指针是个特别好的办法，linked list里面很多题都可以用它来实现。 除了判断circle，快慢指针可以帮助我们找到linked list的中点，对处理回文，merge linkedin list方面都有许多帮助

不知道小帅 发表于 2020-8-26 15:54
方法一里面第10行和11行可以写得更compact一些，
[mw_shl_code=java,true]if (!seen.add(head)) return tr ...

查到了说：
Return Value: The function returns True if the element is not present in the HashSet otherwise False if the element is already present in the HashSet.
原来.add()还有return value!

ahbbzong 发表于 2020-8-26 16:02
快慢指针是个特别好的办法，linked list里面很多题都可以用它来实现。 除了判断circle，快慢指针可以帮助我 ...

不知道是不是我刷题不够多，感觉快慢指针在array里出现的比较少，一到了linked list就有一些linked list-specific的方法出现了，除了快慢指针之外，还有recursion

liuzz10 发表于 2020-8-27 08:06
不知道是不是我刷题不够多，感觉快慢指针在array里出现的比较少，一到了linked list就有一些linked list- ...

其实原因很简单，array 不需要快慢指针这种麻烦办法，array 可以直接access 到任意一个index。一般在linked list里面出现的比较多，这是linked list 里面的一个典型用法。我觉得linked list 和 tree那个模块一样，都自己的套路，需要专项练习

ahbbzong 发表于 2020-8-26 16:09
其实原因很简单，array 不需要快慢指针这种麻烦办法，array 可以直接access 到任意一个index。一般在linked ...

是，刷过一些array的题之后刷linked list感觉落差很大，经验基本不能复用

liuzz10 发表于 2020-8-27 08:12
是，刷过一些array的题之后刷linked list感觉落差很大，经验基本不能复用

我感觉一共就10-20种套路。熟练就好了，大部分题做不出感觉不是不会套路，而是没看出来套路哈哈哈