Title links: leetcode-cn.com/problems/intersection-of-two-linked-lists/

Topic describes

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 problem data guarantees that there are no rings in the chain. After the function returns the result, the list must retain its original structure.

Subject analysis

Two lists intersect, not intersect, so as long as you find the starting node of the intersection, all subsequent nodes are considered to intersect.

As shown in the figure below, the starting node of the intersection is considered to be C1

Code implementation

1. Hash sets

Hash sets are used to store linked list A nodes, and if there are linked list B nodes in the set, it indicates intersection.

2. Dual Pointers

When neither list is empty, create two Pointers pA and pB that initially point to the head nodes of both lists, headA and headB respectively, and then traverse each node of the two lists in turn.

Both Pointers pA and pB need to be updated at each step.

If the pointer pA is not null, the pointer is moved to the next node; If the pointer pB is not null, the pointer is moved to the next node.

If the pointer pA is null, move the pointer to the head node of the linked list headB; If the pointer pB is empty, the pointer is moved to the head node of linked list headA.

When Pointers pA and pB point to the same node or are both null, return the node they point to or null.

/** * hash set ** time complexity: O(m+n), m and n refer to the length of linked list headA and headB respectively * space complexity: O(m) * * @param headA * @param headB * @return */ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> set = new HashSet<ListNode>(); ListNode temp = headA; // headA into the collection while (temp! = null){ set.add(temp); temp = temp.next; } temp = headB; while (temp ! = null){ if(set.contains(temp)){ return temp; } temp = temp.next; } return null; } /** * dual pointer ** time complexity: O(m+n), m and n refer to the length of linked list headA and headB respectively * space complexity: O(1) * * @param headA * @param headB * @return */ public ListNode getIntersectionNode2(ListNode headA, ListNode headB) { if(headA == null || headB == null){ return null; } ListNode pA = headA; ListNode pB = headB; while (pA ! = pB){ pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; }Copy the code