This is the fourth day of my participation in Gwen Challenge

160. Intersecting linked lists

Topic describes

Write a program to find the start node where two singly linked lists intersect.

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

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

link

Leetcode.com/problems/in…

Thinking analytical

You can think of it as having two chains of nodes of different lengths, aligned at the end. Find the head node where the two links begin to overlap.

We can solve this problem by applying a mathematical theorem.

a + b = b + a

The two Pointers traversed from the head of the chain of the two nodes respectively will turn to the head of the other chain once they reach the tail node of their own chain. After a+ B moves, they will reach the tail node of the other chain at the same time.

What is required is a node that is the same distance between the two current chains. Suppose the desired distance from the end node is c, then

a+b-c=b+a-c

So, we just have to design an algorithm with two Pointers to the head of each chain. Iterate until both Pointers point to the same node.

Algorithm implementation

/** * 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){if(a==null){
                a=headB;
            }else{
                a=a.next;
            }
            if(b==null){
                b=headA;
            }else{ b=b.next; }}returna; }}Copy the code

Advanced design

This problem.