This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

Topic Description:

160. Cross Linked List – Force Link (LeetCode) (leetcode-cn.com)

Given the head nodes headA and headB of two singly linked lists, you find and return the starting node where the two singly linked lists intersect. If two lists do not intersect, null is returned.

In the figure, two linked lists intersect at node C1:

The topic data guarantees that there are no rings in the entire chain structure.

Note that after the function returns the result, the list must retain its original structure.

The sample a

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 The intersecting node has a value of 8 (note that it cannot be 0 if two linked lists intersect). Starting from their respective table heads, list A is [4,1,8,4,5] and list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersection 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 output: Intersected at '2' The intersecting node has a value of 2 (note that it cannot be 0 if two linked lists intersect). Counting from the respective table headers, list A is [0,9,1,2,4] and list B is [3,2,4]. In A, there are three nodes before the intersection node; In B, there is 1 node before the intersection node.Copy the code

Example 3

Enter: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Starting from their respective table headers, list A is [2,6,4] and list B is [1,5]. Since these two linked lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. The two lists do not intersect, so null is returned.Copy the code

Thought analysis

Hash set

First, walk through the linked list headA, adding each node to the hash set. We then iterate over the linked list headB to determine whether the current node is in the hash set:

  • If the current node is not in the hash set, the next node is traversed.

  • If the current node is in the hash set, then all subsequent nodes are in the hash set, that is, all nodes from the current node are in the intersection of the two lists, so the first node in the hash set traversed in headB is the node where the two lists intersect, and that node is returned.

If none of the nodes in the list headB are in the hash set, then the two lists do not intersect and null is returned.

AC code

class Solution {
    fun getIntersectionNode(headA:ListNode? , headB:ListNode?).:ListNode? {
        if (null == headA || null == headB) {
            return null
        }
    
        val set = HashSet<ListNode>()
        var pA = headA
        var pB = headB
        while (null! = pA) {set.add(pA)
            pA = pA.next
        }
        while (null! = pB) {if (set.contains(pB)) {
                return pB
            }
            pB = pB.next
        }
        return null}}Copy the code

Double pointer

When neither headA nor headB is empty, two Pointers pA and pB are created, initially pointing to headA and headB respectively, and then the two Pointers are successively traversed through each node of the two lists. Specific practices are as follows:

The pointer pA walks through the list headA, and then starts walking through the list headB. The path pA takes is chain A + chain B

PB traverses the list headB, and then starts traversing the list headA. PB traverses the list B +A

PA and pB both travel the same length, the sum of the lengths of A and B, which is the same as if you align the two chains from the end, and if they intersect, they meet earlier at the intersection, and if they don’t intersect, they meet at the end.

The animation problem can refer to this problem

AC code

class Solution {
    fun getIntersectionNode(headA: ListNode? , headB:ListNode?).: ListNode? {
        if (null == headA || null == headB) {
            return null
        }
        
        var pA = headA
        var pB = headB
        while(pA ! = pB) {// The key to exit is that pA and pB both point to the same pointer (not equal), or both point to null
            pA = if (null == pA) headB else pA.next
            pB = if (null == pB) headA else pB.next
        }
        return pA
    }
}
Copy the code

conclusion

I’ve blown the night breeze you’ve blown

reference

Intersection Linked List – Intersection linked List – Force link (LeetCode) (leetcode-cn.com)

Diagram intersect linked list-Intersect linked list-force link (LeetCode) (leetcode-cn.com)

160. Intersecting Linked List (double pointer, clear diagram) – Intersecting Linked List – Force button (LeetCode) (leetcode-cn.com)