142. Linked List Cycle II

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle( ListNode head ) { if( head == null || head.next == null ){ return null; } // 快指针fp和慢指针sp， ListNode fp = head, sp = head; while( fp != null && fp.next != null){ sp = sp.next; fp = fp.next.next; //此处应该用fp == sp ，而不能用fp.equals(sp) 因为链表为1 2 的时候容易 //抛出异常 if( fp == sp ){ //说明有环 break; } } //System.out.println( fp.val + " "+ sp.val ); if( fp == null || fp.next == null ){ return null; } //说明有环，求环的起始节点 sp = head; while( fp != sp ){ sp = sp.next; fp = fp.next; } return sp; } }

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next==null){ return null; } ListNode fast=head, slow= head; while(fast!=null && fast.next!=null){ fast=fast.next.next; slow =slow.next; if(fast==slow){ break; } } if(fast==slow){ slow = head; while(fast!=slow){ fast=fast.next; slow=slow.next; } return fast; } return null; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。