[PYTHON] Let Code Day 84 starting from zero "142. Linked List Cycle II"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 83 "102. Binary Tree Level Order Traversal" starting from zero

Twitter I'm doing it.

** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!

problem

142. Linked List Cycle Ⅱ The difficulty level is Medium. As was the case last time, this is an excerpt from the problem collection.

The problem is similar to the previously solved Linked List Cycle (https://qiita.com/KueharX/items/20f411ebf1c53cff2208). A linked list is given. Returns the node where the linked list cycle begins. If there is no cycle, null is returned.

To represent a cycle in a given linked list, use the integer pos at the end of the linked list to represent the connecting position (index 0). If pos is -1, there are no cycles in the linked list.

Note: Do not change the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.

solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        root,dic = head,{}
        while root:
            if root in dic:
                return root
            dic[root] = 1
            root = root.next
        return root
# Runtime: 56 ms, faster than 51.83% of Python3 online submissions for Linked List Cycle II.
# Memory Usage: 16.9 MB, less than 51.15% of Python3 online submissions for Linked List Cycle II.

I managed it using a dictionary.

When I reconsidered it later, I felt that it would be easier to understand if I solved it using two pointers, but I think this is fine this time. ~~ It's most important to keep solving !! ~~

So that's it for this time. Thank you for your hard work.