This is the 9th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force buckle algorithm continues to punch card 42 days 🎈!
🚀 Algorithm 🚀

🌲 Example: Intersecting linked lists

Given the head nodes of two singly linked lists, headA and headB, 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

Enter: intersectVal =8, listA = [4.1.8.4.5], listB = [5.0.1.8.4.5], skipA = 2, skipB = 3Output: Intersected at'8'Interpretation: The value of the intersection node is8(Note that if two lists intersect, it cannot be0). Starting from the respective table headers, linked list A is [4.1.8.4.5], linked list B is [5.0.1.8.4.5]. In A, we have theta before the intersecting node2A node; In B, we have theta before the intersecting node3A node.Copy the code

Example 2: 

Enter: intersectVal =2, listA = [0.9.1.2.4], listB = [3.2.4], skipA = 3, skipB = 1Output: Intersected at'2'Interpretation: The value of the intersection node is2(Note that if two lists intersect, it cannot be0). Starting from the respective table headers, linked list A is [0.9.1.2.4], linked list B is [3.2.4]. In A, we have theta before the intersecting node3A node; In B, we have theta before the intersecting node1A node.Copy the code

Example 3

Enter: intersectVal =0, listA = [2.6.4], listB = [1.5], skipA = 3, skipB = 2Output:nullFrom the respective table headers, linked list A is [2.6.4], linked list B is [1.5]. Because the two linked lists do not intersect, intersectVal must be0, and skipA and skipB can be arbitrary values. The two lists do not intersect, so returnnull 。
Copy the code
  • The number of nodes in listA is M
  • The number of nodes in the listB is N
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • If listA and listB do not intersect, intersectVal is 0
  • If there is an intersection between listA and listB, intersecting intersectVal == listA[skipA + 1] == listB[skipB + 1]

🌻C# method: depth-first search

To determine whether two lists intersect, hash sets can be used to store list nodes.

First, the list headA is iterated and each node in the list headA is added to the hash set. We then iterate over the linked list headB and, for each node traversed, determine if the 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 at the intersection of the two lists, so the first node in the hash set traversed in the list headB is the node where the two lists intersect, and that node is returned.

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

Thinking analytical

Code:

public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        ISet<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while(temp ! =null) {
            visited.Add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp ! =null) {
            if (visited.Contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null; }}Copy the code

The execution result

By execution time:124Ms, in all C# beat 65.20% of users in submissionMemory consumption:38.5MB, in all C# beat 15.20% of users in submission
Copy the code

Complexity analysis

Time complexity: O(m+n), where m and n are the lengths of linked list headA and headB respectively. You need to traverse both lists once. Spatial complexity: O(m), where M is the length of linked list headA. A hash set is required to store all the nodes in the linked list headA.Copy the code

🌻Java method 1: hash set

Hash sets can be used to store linked list nodes.

First, the list headA is iterated and each node in the list headA is added to the hash set. We then iterate over the linked list headB and, for each node traversed, determine if the 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 at the intersection of the two lists, so the first node in the hash set traversed in the list headB is the node where the two lists intersect, and that node is returned.

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

Code:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while(temp ! =null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp ! =null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null; }}Copy the code

The execution result

By execution time:7Ms, beat out all Java commits22.83% user memory consumption:42.3MB, beat out all Java commits6.96% of the userCopy the code

Complexity analysis

Time complexity: O(m+n), where m and n are the lengths of linked list headA and headB respectively. You need to traverse both lists once. Spatial complexity: O(m), where M is the length of linked list headA. A hash set is required to store all the nodes in the linked list headA.Copy the code

🌻Java Method 2: dual Pointers

Thinking analytical

Code:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while(pA ! = pB) { pA = pA ==null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        returnpA; }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits100.00% user memory consumption:41.2MB, beat out all Java commits59.13% of the userCopy the code

Complexity analysis

Time: O(m+ N) Space: O(1)
Copy the code

💬 summary

  • Today is the forty-second day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!