I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain.

36th question (question 160)

  1. Intersection of Two Linked Lists

the issue's details

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

img

begin to intersect at node c1.

Example 1:

img

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

img

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

img

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Each value on each linked list is in the range [1, 10^9].
  • Your code should preferably run in O(n) time and use only O(1) memory.

Way of thinking

  1. Make a copy of each to proceed with headA and headB (p, q).
  2. Substitute headB when p goes to the end, and assign headA when q goes to the end.
  3. Loop until p and q are equal or both reach the end.
  4. Returns null if it's terminating, and that node if it's equal.

Answer code

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        
        p,q = headA , headB 
        while p and q and p != q :
            p = p.next
            q = q.next
            if p == q :
                return q
            if not p :
                p = headB
            if not q :
                q = headA
        return p

--I'll write it in Go too!

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	A := headA
	B := headB

	for A != B {
		if A == nil {
			A = headB
		} else {
			A = A.Next
		}
		if B == nil {
			B = headA
		} else {
			B = B.Next
		}
	}
	return A
}

Recommended Posts

I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 7. Reverse Integer (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 112. Path Sum (Python, Go)
I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 13. Roman to Integer (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 121 Best Time to Buy and Sell Stock (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
Let Code Day 35 "160. Intersection of Two Linked Lists" Starting from Zero
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
I tried Grumpy (Go running Python).
I tried hundreds of millions of SQLite with python
I tried running faiss with python, Go, Rust
I tried to summarize how to use matplotlib of python
[OpenCV / Python] I tried image analysis of cells with OpenCV
[Python] I tried to get Json of squid ring 2
I tried using Python (3) instead of a scientific calculator
I tried "morphology conversion" of images with Python + OpenCV
I tried to summarize the string operations of Python
I tried Python> autopep8
I tried Python> decorator
I tried to find the entropy of the image with python
I tried "gamma correction" of the image with Python + OpenCV
I tried the accuracy of three Stirling's approximations in python
I tried running Movidius NCS with python of Raspberry Pi3
Automatic scraping of reCAPTCHA site every day (1/7: python environment construction)
[Python] I tried to visualize the follow relationship of Twitter
[Python] I tried collecting data using the API of wikipedia
I tried a stochastic simulation of a bingo game with Python
I tried to implement blackjack of card game in Python
I tried fp-growth with python
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
I tried to make a regular expression of "amount" using Python
I tried to make a regular expression of "time" using Python
I tried to create a list of prime numbers with python
I tried to make a regular expression of "date" using Python
I tried to fix "I tried stochastic simulation of bingo game with Python"
I tried to improve the efficiency of daily work with Python
I tried to automatically collect images of Kanna Hashimoto with Python! !!
I tried to make a mechanism of exclusive control with Go