LeetCode142：巧解链表环入口(多解)
)
题目LeetCode142给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。Python解法1.哈希表class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: visited [] while head: if head in visited: return head else: visited.append(head) head head.next return None逐个遍历重复直接为所求2.快慢指针class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: if not head: return None slow head fast head while fast: slow slow.next if fast.next: fast fast.next.next else: return None if slow fast: ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptr return None解法二的关键在于if slow fast: ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptrJava解法1.哈希表public class Solution{ public ListNode detectCycle(ListNode head){ ListNode pos head; SetListNode visited new HashSetListNode(); while(pos ! null){ if(visited.contains(pos)){ return pos; }else{ visited.add(pos); } pos pos.next; } return null; } }2.快慢指针public class Solution { public ListNode detectCycle(ListNode head) { if(head null){ return null; } ListNode slow head; ListNode fast head; while(fast ! null){ slow slow.next; if(fast.next ! null){ fast fast.next.next; }else{ return null; } if(slow fast){ ListNode ptr head; while(slow ! ptr){ slow slow.next; ptr ptr.next; } return ptr; } } return null; } }C解法1.哈希表class Solution{ public: ListNode *detectCycle(ListNode *head){ ListNode *pos head; unordered_setListNode * visited; while(pos ! nullptr){ if(visited.count(pos)){ return pos; }else{ visited.insert(pos); } pos pos-next; } return nullptr; } };2.快慢指针class Solution{ public: ListNode *detectCycle(ListNode *head){ if(head nullptr){ return nullptr; } ListNode *slow head; ListNode *fast head; while(fast ! nullptr){ slow slow-next; if(fast-next ! nullptr){ fast fast-next-next; }else{ return nullptr; } if(slow fast){ ListNode *ptr head; while(slow ! ptr){ slow slow-next; ptr ptr-next; } return ptr; } } return nullptr; } };
