Sword refers to Offer 52. The first common node of two linked lists

Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

1. Title 📑

Enter two linked lists to find their first common node.

Here are two linked lists:

The intersection begins at node C1.

Example 1:

Enter: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

Output: Reference of the node with value = 8

Input explanation: 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.

Example 2:

Enter: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output: Reference of the node with value = 2

Input explanation: 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.

Example 3:

Enter: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

Output: null

Input explanation: from the respective table 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 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.
  • Question 160 is the same as that in the main station: leetcode-cn.com/problems/in…

2. Ideas 🧠

Method 1: double pointer

In general, it is very convenient to insert and delete linked lists with double Pointers, but it is very tedious to insert and delete arrays in a certain location.

  1. The length of linked list A is L1+C, and that of linked list B is L2+C, where C is the length of the common part of the two lists.
  2. After list A has taken L1+C steps, go back to the start of list B and take L2 steps. After list B has gone L2+C, go back to the start of list A and go L1. The list meets when the number of steps is L1+L2+C.
  3. The list meets when the number of steps is L1+L2+C.
    • If the two listsThere areCommon tail (i.e. C > 0) : pointerA , BIt also points to a public nodenode 。
    • If the two listsThere is noCommon tail (i.e. C = 0) : pointerA , BAlso point to null.

Less nonsense ~~~~~ on the code!

3. Code: 👨💻

Commit AC for the first time

/** * 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 A = headA;
        ListNode B = headB;
        while(A ! = B) { A = A ==null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        returnA; }}Copy the code

Time complexity: O(m + n) m represents the length of l1 and n represents the length of L2

Space complexity: O(1)

4, summarize

The biggest difficulty of this topic is whether to understand the structure of the linked list, understand the double pointer, for beginners double pointer is a very headache.

5. Related operations of linked lists

Link to 🔗

18. Remove list nodes – nuggets

Leetcode 21. Merge two ordered lists – nuggets

Leetcode 83. Remove duplicate elements from sorted lists – nuggets

22. The k node from the bottom of the list – nuggets

Sword finger Offer 24. Reverse the list – nuggets

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

52. The first common node of two linked lists