current position:Home>leetcode 160. Intersection of Two Linked Lists (python)
leetcode 160. Intersection of Two Linked Lists (python)
2022-01-30 19:47:56 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 1 God , Check out the activity details :2021 One last more challenge 」
describe
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
- intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
- listA - The first linked list.
- listB - The second linked list.
- skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
- skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.
The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.
Follow up: Could you write a solution that runs in O(n) time and use only O(1) memory?
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
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.
Copy code
Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
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.
Copy code
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
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.
Copy code
Note:
The number of nodes of listA is in the m.
The number of nodes of listB is in the n.
0 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.
Copy code
analysis
According to the meaning , Is to give the head nodes of two linked lists headA and headB , If the two linked lists intersect, let's find the intersecting node , If it doesn't intersect, return directly None Just go . The problem also makes it more difficult for us , We are required to be in O(1) Complete the problem requirements under the level of memory .
The idea is simple , The simplest way is to traverse two linked lists headA and headB Calculate their length difference d , Let the longer one go forward first d Nodes , Then the two linked lists go back at the same time , If there are intersecting nodes, the pointers must be equal , No intersection is found after traversal .
answer
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if not headA or not headB: return None
len_a = self.getLen(headA)
len_b = self.getLen(headB)
diff = abs(len_a-len_b)
for i in range(diff):
if len_a>len_b:
headA = headA.next
else:
headB = headB.next
while headA and headB:
if headA == headB:
return headA
headA = headA.next
headB = headB.next
return None
def getLen(self, L):
result = 0
while L:
result += 1
L = L.next
return result
Copy code
Running results
Runtime: 212 ms, faster than 46.07% of Python online submissions for Intersection of Two Linked Lists.
Memory Usage: 43.3 MB, less than 58.63% of Python online submissions for Intersection of Two Linked Lists.
Copy code
analysis
Another solution is to look at leetcode Written by the great God in the Forum , And its cleverness .
- With a pointer a Point to headA , With a pointer b Point to headB
- When a It's not equal to b When , Keep going while loop , Two linked lists traverse backward at the same time , If a If it is not empty, continue to traverse a node after the next , If a If it is empty, let a Pointer to headB ; If b If it is not empty, continue to traverse a node after the next , If b If it is empty, let b Pointer to headA
- Because the first traversal eliminates the length difference between the two linked lists , So if the two intersect , In the second traversal, you must find a == b The node of , If the two don't intersect , be a and b The traversal results must be None
answer
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if not headA or not headB: return None
a = headA
b = headB
while a != b:
if not a :
a = headB
else:
a = a.next
if not b:
b = headA
else:
b = b.next
return a
Copy code
Running results
Runtime: 196 ms, faster than 75.21% of Python online submissions for Intersection of Two Linked Lists.
Memory Usage: 43.4 MB, less than 39.90% of Python online submissions for Intersection of Two Linked Lists.
Copy code
Original link :leetcode.com/problems/in…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201301947541425.html
The sidebar is recommended
- Exploratory data analysis (EDA) in Python using SQL and Seaborn (SNS).
- Turn audio into shareable video with Python and ffmpeg
- Using rbind in python (equivalent to R)
- Pandas: how to create an empty data frame with column names
- Talk about quantifying investment using Python
- Python, image restoration in opencv - CV2 inpaint
- Python notes (14): advanced technologies such as object-oriented programming
- Python notes (13): operations such as object-oriented programming
- Python notes (12): inheritance such as object-oriented programming
- Chapter 2: Fundamentals of python-5 Boolean
guess what you like
-
Python notes (11): encapsulation such as object-oriented programming
-
Python notes (10): concepts such as object-oriented programming
-
Gradient lifting method and its implementation in Python
-
Van * Python | simple crawling of a site course
-
Chapter 1 preliminary knowledge of pandas (list derivation and conditional assignment, anonymous function and map method, zip object and enumerate method, NP basis)
-
Nanny tutorial! Build VIM into an IDE (Python)
-
Fourier transform of Python OpenCV image processing, lesson 52
-
Introduction to python (III) network request and analysis
-
China Merchants Bank credit card number recognition project (Part I), python OpenCV image processing journey, Part 53
-
Introduction to python (IV) dynamic web page analysis and capture
Random recommended
- Python practice - capture 58 rental information and store it in MySQL database
- leetcode 119. Pascal's Triangle II(python)
- leetcode 31. Next Permutation(python)
- [algorithm learning] 807 Maintain the city skyline (Java / C / C + + / Python / go / trust)
- The rich woman's best friend asked me to write her a Taobao double 11 rush purchase script in Python, which can only be arranged
- Glom module of Python data analysis module (1)
- Python crawler actual combat, requests module, python realizes the full set of skin to capture the glory of the king
- Summarize some common mistakes of novices in Python development
- Python libraries you may not know
- [Python crawler] detailed explanation of selenium from introduction to actual combat [2]
- This is what you should do to quickly create a list in Python
- On the 55th day of the journey, python opencv perspective transformation front knowledge contour coordinate points
- Python OpenCV image area contour mark, which can be used to frame various small notes
- How to set up an asgi Django application with Postgres, nginx and uvicorn on Ubuntu 20.04
- Initial Python tuple
- Introduction to Python urllib module
- Advanced Python Basics: from functions to advanced magic methods
- Python Foundation: data structure summary
- Python Basics: from variables to exception handling
- Python notes (22): time module and calendar module
- Python notes (20): built in high-order functions
- Python notes (17): closure
- Python notes (18): decorator
- Python notes (16): generators and iterators
- Python notes (XV): List derivation
- Python tells you what timing attacks are
- Python -- file and exception
- [Python from introduction to mastery] (IV) what are the built-in data types of Python? Figure out
- Python code to scan code to pay attention to official account login
- [algorithm learning] 1221 Split balanced string (Java / C / C + + / Python / go / trust)
- Python notes (22): errors and exceptions
- Python has been hidden for ten years, and once image recognition is heard all over the world
- Python notes (21): random number module
- Python notes (19): anonymous functions
- Use Python and OpenCV to calculate and draw two-dimensional histogram
- Python, Hough circle transformation in opencv
- A library for reading and writing markdown in Python: mdutils
- Datetime of Python time operation (Part I)
- The most useful decorator in the python standard library
- Python iterators and generators