This is the 11th day of my participation in the genwen Challenge

The title

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:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 output: Intersected at ‘8’ 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:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 output: Intersected at ‘2’ 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:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 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. The two lists do not intersect, so null is returned.

Their thinking

The linked list is divided into two sections, one is a before the intersection, b is different, and the other is c after the intersection

So when the pointer to list A moves to the end of list A, it moves the pointer to the beginning of list B. Same thing with linked list B

The distance traveled by Pointers A and B is a+b+ C, and that’s where they intersect. If there is no intersection, their distance is a+ B, and the two Pointers end up at the end of both lists

code

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
func getIntersectionNode(headA, headB *ListNode) *ListNode {

	
    oa,ob:=headA,headB
	forheadB! =headA {if headA==nil{

			headA=ob
		}else {

			headA=headA.Next
		}
		if headB==nil{

			headB=oa
		}else{
			headB=headB.Next
		}
	}
	return headA

}
Copy the code