星星博客 »  > 

剑指23

题目:

返回链表中环的入口节点:(leetcode 142)
在这里插入图片描述

思路:

1.求得位于环中的某个节点
2.通过这个节点的next求的环的长度n
3.双指针,fast指针先移动n个位置,此时,fast和head同时移动,他们首次相遇的位置就是环的入口节点

这个我写的时候,fast = fast.next,如果和2.1类似,那么就不用中间计算长度的过程了!

还有一种思路:
1.都从head开始走,fast每次走两步,slow每次走一步。最终相遇
2.head从头走,meet从此处开始走,每次走一步,最终相遇点就是入口点

不管怎么走都要画图。

代码:

/**
 * 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 pHead) {
        //1.找到环中的一个点,不相等的话,fast每次多走一
        ListNode node = findListNode(pHead);
        if (node == null) {
            return null;
        }
        //2.根据这个点确定环的长度
        int length = 0;
        ListNode meetNode = node;
        while (node.next != meetNode) {
            node = node.next;
            length++;
        }
        //3.快慢指针首次相遇点即环的入口
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (length-- >= 0) {
            fast = fast.next;
        }
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }


    private ListNode findListNode(ListNode pHead) {
        if(pHead == null){
            return null;
        }
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while (fast != null && slow != null) {
            if (slow == fast) {
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
            if(fast!=null){
                fast = fast.next;
            }
        }
        return null;
    }
}
/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode meet = null;
        while(fast != null && slow != null){
            if(fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                meet = fast;
                break;
            }
        }
        if(meet == null) return null;
        while(meet != head){
            head = head.next;
            meet = meet.next;
        }
        return meet;
    }
}

相关文章