LC-141andLC-142

142. 环形链表 II

思路：

设链表共有 a+b 个节点，其中链表头部到链表入口有 a 个节点（不计链表入口节点），链表环有 b 个节点。

再设两指针分别走了 f，s 步，则有：

f = 2sf=2s；
fast 比 slow多走了 n 个环的长度，即 f = s + nbf=s+nb；
以上两式相减得：f = 2nbf=2nb，s = nbs=nb；

概括一下：

根据：

f=2s （快指针每次2步，路程刚好2倍）
f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb

从head结点走到入环点需要走： a + nb，而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？从head开始，和slow指针一起走，相遇时刚好就是a步。

Java实现

/**

 * 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, slow = head;

        while(true) {

            if(fast == null || fast.next == null) return null;

            fast = fast.next.next;

            slow = slow.next;

            if(fast == slow) break;

        }

        fast = head;

        while (fast != slow){

            fast = fast.next;

            slow = slow.next;

        }

        return fast;

    }

}

Python实现

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def detectCycle(self, head):

        fast, slow = head, head

        while True:

            if not (fast and fast.next): return

            fast, slow = fast.next.next, slow.next

            if fast == slow: break

        fast = head

        while fast != slow:

            fast, slow = fast.next, slow.next

        return fast

141. 环形链表

142少去算法部分。单纯用快慢指针判断是否相遇即刻。

Java实现

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public boolean hasCycle(ListNode head) {

        ListNode fast = head, slow = head;

        while(true) {

            if(fast == null || fast.next == null) return false;

            fast = fast.next.next;

            slow = slow.next;

            if(fast == slow) return true;

        }

    }

}

Python实现

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def hasCycle(self, head: Optional[ListNode]) -> bool:

        fast, slow = head, head

        while True:

            if not (fast and fast.next): return False

            fast = fast.next.next

            slow = slow.next

            if fast == slow: return True

巴特西

LC-141andLC-142

142. 环形链表 II

141. 环形链表

最新文章

热门文章