Location>code7788 >text

160. Intersecting linked tables Golang implementation

Popularity:70 ℃/2024-10-22 11:51:10

Title Description:

Given the head nodes headA and headB of two single linked tables, find and return the starting node of the intersection of the two single linked tables. If there is no intersection node, return null.

Note that intersecting nodes here denote nodes with the same value and physical location, not just the same value.

Thought Analysis:

Assuming that the lengths of chainA and chainB are lenA and lenB respectively, the marvelous thing about this method is that when pA is traversed to the end (i.e., pA == nil), it is redirected to headB to continue traversing. Similarly, when pB reaches the end, it is redirected to headA to continue traversing. Thus, when the two pointers meet, they have synchronized to the same starting point and point to the first common node.
If the same node exists in both linked lists, then the traversal should traverse the length of both linked lists until the two pointers meet.

Click to view code
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA==nil || headB==nil{
        return nil
    }
    pa,pb := headA,headB
    for pa!=pb {
        if pa!=nil{
            pa = 
        }else {
            pa = headB
        }

        if pb!=nil{
            pb = 
        }else {
            pb = headA
        }
    }
    return pa
}