LeetCode - Easy - 141. Linked List Cycle

雨点打透心脏的1/2处 2022-12-29 00:10 204阅读 0赞

## Topic ##

*  Two Pointers
 *  Linked List

## Description ##

[https://leetcode.com/problems/linked-list-cycle/][https_leetcode.com_problems_linked-list-cycle]

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail’s `next` pointer is connected to. **Note that `pos` is not passed as a parameter**.

Return `true` if there is a cycle in the linked list. Otherwise, return `false`.

**Example 1**:

![34e232f8530c309fbbb5e4121998b0cd.png][]

Input: head = [3,2,0,-4], pos = 1
    Output: true
    Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

**Example 2**:

![5613d64632323b0f0987cc31d360f8fb.png][]

Input: head = [1,2], pos = 0
    Output: true
    Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

**Example 3**:

![0046ffffe7c710782a43cecfad50e5ae.png][]

Input: head = [1], pos = -1
    Output: false
    Explanation: There is no cycle in the linked list.

**Constraints**:

*  The number of the nodes in the list is in the range \[0, 10⁴\].
 *  \-10⁵ <= Node.val <= 10⁵
 *  pos is -1 or a valid index in the linked-list.

**Follow up**: Can you solve it using O(1) (i.e. constant) memory?

## Analysis ##

方法一：我写的方法

两指针p1、p2，每次循环中，p1走1步，p2走1步，再走1步，其间判断p1、p2是否相等。若相等，则链有环。若p2为null，则没有。

--------------------

方法二：别人写的方法

1.  Use two pointers, walker and runner.
2.  walker moves step by step. runner moves two steps at time.
3.  if the Linked List has a cycle walker and runner will meet at some point.

## Submission ##

import com.lun.util.SinglyLinkedList.ListNode;
    
    public class LinkedListCycle { 
    	// 方法一：我写的方法
    	public boolean hasCycle1(ListNode head) { 
    		if (head == null)
    			return false;
    		ListNode p1 = head, p2 = head.next;
    
    		while (true) { 
    			if (p2 == null)
    				break;
    
    			if (p1 == p2) { 
    				return true;
    			} else { 
    				p1 = p1.next;
    				p2 = p2.next;
    				if (p2 == null) { 
    					break;
    				} else { 
    					if (p1 == p2)
    						return true;
    					p2 = p2.next;
    				}
    			}
    		}
    
    		return false;
    	}
    
    	// 方法二：别人写的方法
    	public boolean hasCycle2(ListNode head) { 
            ListNode walker = head;
            ListNode runner = head;
            while(runner != null && runner.next != null) { 
                walker = walker.next;
                runner = runner.next.next;
                if(walker == runner) return true;
            }
            return false;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.SinglyLinkedList.ListNode;
    
    public class LinkedListCycleTest { 
    
    	@Test
    	public void test1() { 
    		LinkedListCycle obj = new LinkedListCycle();
    		ListNode node1 = new ListNode(3), node2 = new ListNode(2), 
    				node3 = new ListNode(0), node4 = new ListNode(-4);
    		
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		node4.next = node2;
    		
    		assertTrue(obj.hasCycle1(node1));
    		assertTrue(obj.hasCycle2(node1));
    	}
    	
    	@Test
    	public void test2() { 
    		LinkedListCycle obj = new LinkedListCycle();
    		ListNode node1 = new ListNode(1), node2 = new ListNode(2);
    		
    		node1.next = node2;
    		node2.next = node1;
    		
    		assertTrue(obj.hasCycle1(node1));
    		assertTrue(obj.hasCycle2(node1));
    	}
    	
    	@Test
    	public void test3() { 
    		LinkedListCycle obj = new LinkedListCycle();
    		ListNode node1 = new ListNode(1);
    		
    		assertFalse(obj.hasCycle1(node1));
    		assertFalse(obj.hasCycle2(node1));
    	}
    }

[https_leetcode.com_problems_linked-list-cycle]: https://leetcode.com/problems/linked-list-cycle/
[34e232f8530c309fbbb5e4121998b0cd.png]: /images/20221120/a7405cc6d44b4236b26f187beaaa2808.png
[5613d64632323b0f0987cc31d360f8fb.png]: /images/20221120/ea405dc4a7fc450a99410b9be5d1a789.png
[0046ffffe7c710782a43cecfad50e5ae.png]: /images/20221120/ee6785aa8bd64bb58d5a679d3f526c5b.png