“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

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, Reads as [4,1,8,4,5]. 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 the 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 the code

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: No intersection Explanation: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 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 the 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 the code

parsing

If the two lists intersect, let’s find which one. If they don’t, return None. The problem also increased the difficulty for us, requiring us to complete the problem in O(1) level of memory.

The simplest way is to traverse two lists, headA and headB, and calculate their length difference D. Let the longer list traverse D nodes first, and then the two lists go back at the same time. If the nodes have intersected, the Pointers must be equal.

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 the code

The results

Given in the Python online submissions for Intersection of Two Linked Lists. Submissions in Python online submissions for Intersection of Two Linked Lists.Copy the code

parsing

Another solution is written by the great god of Leetcode’s forum, and it is very clever.

  • Use pointer A to point to headA, and use pointer B to point to headB
  • When a is not equal to b, we keep doing a while loop where both lists are iterated backwards at the same time. If a is not empty, we continue to iterate over a node. If a is empty, we make a pointer to headB. If b is not empty, proceed through a node, and if b is empty, make the b pointer point to headA
  • Because the first traversal eliminates the length difference between the two lists, if they intersect, the second traversal is bound to find a node where A == b. If they do not intersect, the traversal result of both a and B is bound to 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 aCopy the code

The results

Linked Lists in the Linked submissions. Memory Usage: 10000 ms. Submissions in Python online submissions for Intersection of Two Linked Lists.Copy the code

Original link: leetcode.com/problems/in…

Your support is my biggest motivation