Topic describes

160. Intersecting linked lists

Write a program to find the start node where two singly linked lists intersect.

Here are two linked lists:

The intersection begins at node C1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Reference of the node with value = 8 Reference of the node with value = 8 Starting from their respective table headers, linked list A is [4,1,8,4,5] and linked list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersecting node; In B, there are three nodes before the intersection node.Copy the code

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Reference of the node with value = 2; Reference of the node with value = 2; Starting from their respective table headers, linked list A is [0,9,1,2,4] and linked list B is [3,2,4]. In A, there are three nodes before the intersecting node; In B, there is 1 node before the intersecting node.Copy the code

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 output: null From their respective headers, linked list A is [2,6,4] and linked list B is [1,5]. Because the two linked lists do not intersect, intersectVal must be 0, and skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so null is returned.Copy the code

Note:

  • If two lists do not intersect, null is returned.
  • After the result is returned, both lists must remain in their original structure.
  • It can be assumed that there are no loops in the entire list structure.
  • The program meets the O(n) time complexity as far as possible and uses only O(1) memory.

Their thinking

To find the starting node where two singly linked lists intersect, we can solve this problem in the following ways:

notation

While traversal is carried out twice for two linked lists, first traversing one list, adding a flag bit to each node in the list, and then traversing the other list. If traversing reaches the first node that has been marked, it is the starting node of the intersection of the two linked lists.

If no marked node is found after traversal, the two linked lists are disjoint and null is returned.

Double pointer method

Initialize two Pointers pA and pB to point to headA and headB respectively. Each time pA and pB move one step. When pA hits bottom, it changes track to headB, similarly, when pB hits bottom, it changes track to headA. This simply iterates (the non-public part of A + the non-public part of B + the common part of AB).

The problem solving code

notation

var getIntersectionNode = function(headA, headB) {
    while(headA) {
        headA.flag = true
        headA = headA.next
    }
    while(headB) {
        if (headB.flag) return headB
        headB = headB.next
    }
    return null
};
Copy the code

Double pointer method

var getIntersectionNode = function(headA, headB) { var pA = headA; var pB = headB; while(pA ! == pB){ pB = pB? pB.next: headA; pA = pA? pA.next: headB; } return pA; };Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

[LeetCode367 problem effective completely square number] | punch brush

[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign