The first common node of two linked lists

sequence

This article documents the first common node of two leetcode lists

The title

Enter two linked lists to find their first common node.

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 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.

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 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.

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.

Note:

If two lists do not intersect, null is returned. After the result is returned, both lists must retain 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. The same subject and the main questions 160: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/Copy the code

Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Answer key

/**
 * 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 c1 = headA;
        ListNode c2 = headB;
        while (c1 !=  c2) {
            c1 = c1 == null ? headB : c1.next;
            c2 = c2 == null ? headA : c2.next;
        }

        return c1;
    }
}
Copy the code

summary

The overall idea is to join the linked lists behind the two lists (because the title requires that the two lists must maintain the original structure, so the traversal pointer is changed when traversing again), and then traverse at the same time to judge whether the nodes are equal. If they are equal, it means that the common node is found. If none is found, both c1 and c2 are null, the loop is broken, and null is returned

doc