leetcode 160. Intersection of Two Linked Lists （python）

「 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