Topic describes

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

The two linked lists intersect at node C1:

The problem data guarantees that there are no rings in the chain.

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

 

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 output: Intersected at '8' The value of the intersection node is 8 (note that it cannot be 0 if two lists intersect). 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 output: Intersected at '2' The value of the intersection node is 2 (note that it cannot be 0 if two lists intersect). 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 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. The two lists do not intersect, so null is returned.Copy the code

 

Tip:

  • listAThe number of nodes ism
  • listBThe number of nodes isn
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • iflistA 和 listBThere’s no intersection,intersectVal 为 0
  • iflistA 和 listBHave a intersection point,intersectVal == listA[skipA + 1] == listB[skipB + 1]

 

Advanced: Can you design a solution with O(n) time complexity and only O(1) memory?

 

Note: leetcode-cn.com/problems/in…

solution

Use two Pointers (cur1, cur2) to two linked lists, headA and headB.

At the same time, the linked list is traversed. When CUR1 reaches the end of linked list headA, it is repositioned to the head node of linked list headB. When CUR2 reaches the end of linked list headB, relocate to the head node of linked list headA.

If two Pointers meet, the node they point to is the first common node. If they do not meet, the two lists have no common nodes, and both Pointers point to NULL.

Python3

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: cur1, cur2 = headA, headB while cur1 ! = cur2: cur1 = headB if cur1 is None else cur1.next cur2 = headA if cur2 is None else cur2.next return cur1Copy the code

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA, cur2 = headB;
        while (cur1 != cur2) {
            cur1 = cur1 == null ? headB : cur1.next;
            cur2 = cur2 == null ? headA : cur2.next;
        }
        return cur1;
    }
}
Copy the code

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur1 = headA;
        ListNode* cur2 = headB;
        while (cur1 != cur2) {
            cur1 = cur1 ? cur1->next : headB;
            cur2 = cur2 ? cur2->next : headA;
        }
        return cur1;
    }
};
Copy the code

JavaScript

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let cur1 = headA; let cur2 = headB; while (cur1 ! = cur2) { cur1 = cur1 ? cur1.next : headB; cur2 = cur2 ? cur2.next : headA; } return cur1; };Copy the code