首页 > 代码库 > [leetcode]Linked List Cycle

[leetcode]Linked List Cycle

2024-07-12 21:57:40   226人阅读

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?

算法

思路1：

快慢指针，当两个指针相遇，则表示有环，否则则无环，可能需要多遍遍历，空间复杂度O(1)，时间复杂度O(n)

 1 public class Solution { 2     public boolean hasCycle(ListNode head) { 3         if(head == null) return false; 4         ListNode fast = head; 5         ListNode slow = head; 6         while(true){ 7             if(fast.next == null || fast.next.next == null) return false; 8             fast = fast.next.next; 9             slow = slow.next;10             if(fast == slow) return true;11         }12     }13 }

 

思路2：

hash表，当某个节点有两个前驱，则该节点是环的起点，而且只需一次遍历，空间复杂度O(n)，时间复杂度O(n)

 1 public class Solution { 2     public boolean hasCycle(ListNode head) { 3         if(head == null) return false; 4         ListNode tem = new ListNode(0); 5         tem.next = head; 6         Map<ListNode,ListNode> hash = new HashMap<ListNode,ListNode>(); 7         while(true){ 8             if(tem.next == null) return false; 9             if(hash.get(tem.next) != null) return true;10             hash.put(tem.next,tem);11             tem = tem.next;12         }13     }14 }

思路２同样是Linked List Cycle II的解法

 

ListNode的结构如下：

1 public class ListNode {2     int val;3     ListNode next;4     ListNode(int x){5         val = x;6         next = null;7     }8 }
View Code


联系
我们