160.Intersection-of-Two-Linked-Lists.en.md

Problem (160. (Linked list)

https://leetcode.com/problems/intersection-of-two-linked-lists/

Title description

Write a program to find the starting node where two single-linked lists intersect.

Pre-knowledge

-Linked list -Double pointer

Solution 1: Hash method

There are two linked lists A and B. First traverse one of them, such as the linked list A, and store all the nodes in A in the hash table.

Traverse the B linked list to check if the node is in the hash table. The first one that exists is the intersecting node.

-Pseudo code

Data = new Set()// Store the addresses of all nodes in the A linked list

While A is not empty{
Add the current node of the A linked list to the hash table
A Pointer moves backward
}

While B is not empty{
if if the hash table contains the current node of the B linked list
return B
B Pointer moves backward
}

Return null // There is no intersection point between the two linked lists

-Code support: JS

JS Code:

let data = new Set();
while (A ! == null) {
data. add(A);
A = A. next;
}
while (B ! == null) {
if (data. has(B)) return B;
B = B. next;
}
return null;

Complexity analysis

-Time complexity:$O(N)$ -Spatial complexity:$O(N)$

Solution 2: Double pointer

-For example, use two pointers A and B to point to the two linked lists A and B, and the two pointers move backwards at the same speed., -When a reaches the end of the linked list, relocate to the head node of linked list B -When b reaches the end of the linked list, relocate to the head node of linked list A. The point where the -a, b pointers meet is the starting node of the intersection, otherwise there is no intersection point

(Figure 5)

Why must the point where the pointers a and b meet be the starting node of the intersection? Let's prove it：

1. Continue to truncate the two linked lists according to the starting node where they intersect. Linked list 1 is: A + C, and linked list 2 is: B + C
2. When the a pointer finishes traversing the linked list 1, relocate to the head node of the linked list B, and then continue traversing until the intersection point (the distance traversed by the a pointer is A + C + B)
3. Similarly, the distance traversed by the b pointer is B + C + A

-Pseudo code

a = headA
b = headB
While a, b pointers are not equal {
If the a pointer is empty
Relocate the a pointer to the head node of the linked list B
else
a pointer moves one bit backward
If the b pointer is empty
The b pointer is repositioned to the head node of the linked list A
else
b pointer moves one bit backward
}
return a

-Code support: JS, Python, Go, PHP

JS Code:

var getIntersectionNode = function (headA, headB) {
let a = headA,
b = headB;
while (a ! = b) {
a = a === null ? headB : a. next;
b = b === null ? headA : b. next;
}
return a;
};

Python Code：

class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
a, b = headA, headB
while a ! = b:
a = a. next if a else headB
b = b. next if b else headA
return a

Go Code:

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// a= A (a separate part) + C (a intersecting part); b= B (b separate part) + C (b intersecting part)
// a+b=b+a=A+C+B+C=B+C+A+C
a := headA
b := headB
for a ! = b {
if a == nil {
a = headB
} else {
a = a. Next
}
if b == nil {
b = headA
} else {
b = b. Next
}
}
return a
}

PHP Code:

/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution
{
/**
* @param ListNode $headA
* @param ListNode $headB
* @return ListNode
*/
function getIntersectionNode($headA, $headB)
{
$a = $headA;
$b = $headB;
while ($a ! == $b) {// Note, use it here! ==
$a = $a ? $a->next : $headB;
$b = $b ? $b->next : $headA;
}
return $a;
}
}

Complexity analysis

-Time complexity:$O(N)$ -Spatial complexity:$O(1)$