[PYTHON] Let Code Day 35 "160. Intersection of Two Linked Lists" Starting from Zero

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.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 34 "118. Pascal's Triangle" starting from zero

Basically, I would like to solve the easy acceptance in descending order.

Twitter I'm doing it.

problem

160. Intersection of Two Linked Lists

This is the penultimate question of the Easy question in Top 100 Liked Questions.

The problem is to find the node where the intersection of the two unidirectional linked lists begins.

An example is explained in the figure, and it is not possible to post it directly here due to various circumstances, so we would appreciate it if you could check each one.

solution

If you write this at first

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        
        LNA = headA
        LNB = headB
        while LNA != LNB:
            if LNA == None:
                LNA = headB
            else:
                LNA.next
            
            if LNB == None:
                LNB == headA
            else:
                LNB.next
        return LNA
# Time Limit Exceeded

Since the time has expired, I tried to rewrite while and later in the comprehension as follows, and I was able to go.

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        
        LNA = headA
        LNB = headB
        while LNA != LNB:
            LNA = headB if LNA == None else LNA.next
            LNB = headA if LNB == None else LNB.next
        return LNA
# Runtime: 168 ms, faster than 75.08% of Python3 online submissions for Intersection of Two Linked Lists.
# Memory Usage: 29.1 MB, less than 100.00% of Python3 online submissions for Intersection of Two Linked Lists.

You can use BruteForce, HashMap, or Two Pointer to solve the official explanation of this problem! It is. If you are interested, I recommend you to check it.

This way of writing is better! I wrote it in this language! If you have any questions, please feel free to comment.