[Go] Linked List - Intersection Of Two Linked List

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

 

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

 

Constraints:

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA < m
• 0 <= skipB < n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

 

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

 

My code(One way)

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	s := struct{}{}
	a := make(map[*ListNode]struct{})
	for headA != nil {
		a[headA] = s
		headA = headA.Next
	}

	for headB != nil {
		if _, ok := a[headB]; ok {
			return headB
		}
		headB = headB.Next
	}
	return nil
}

https://go.dev/play/p/DwS5Yi9LKTu

• This code will allocate headA to map
• Later headB address will be checked if it is in map or not.
• But this takes much memory.

My code(Two pointer)

https://go.dev/play/p/8-9-_YhN0Of

• This code uses two pointer.
• first if sentence will check headA is nil or not.
• if so, headA address will be checked in map a.
• if not, headA will be allocated to map.
• after this headA if, headB also does same process.
• when they are nil, it will return nil.

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	s := struct{}{}
	a := make(map[*ListNode]struct{})
	for {
		if headA != nil {
			if _, ok := a[headA]; ok {
				return headA
			} else {
				a[headA] = s
				headA = headA.Next
			}
		}
		if headB != nil {
			if _, ok := a[headB]; ok {
				return headB
			} else {
				a[headB] = s
				headB = headB.Next
			}
		}
		if headA == nil && headB == nil {
			break

		}
	}
	return nil
}

sample 16 ms submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pa, pb := headA, headB
    for pa != pb {
        if pa == nil {
            pa = headB
        } else {
            pa = pa.Next
        }
        
        if pb == nil {
            pb = headA
        } else {
            pb = pb.Next
        }
    }
    
    return pa
}

func OLD_getIntersectionNode(headA, headB *ListNode) *ListNode {
    visited := map[*ListNode]struct{}{}
    for {
        if headA != nil {
            if _, seen := visited[headA]; seen {
                return headA
            }
            
            visited[headA] = struct{}{}
            headA = headA.Next
        }
        
        if headB != nil {
            if _, seen := visited[headB]; seen {
                return headB
            }
            
            visited[headB] = struct{}{}
            headB = headB.Next
        }
        
        if headA == nil && headB == nil {
            break
        }
    }
    
    return nil
}

• This code is so simple.
• pa, pb will have headA, headB.
• for loop will stop when they meet.
• It doesn't use map, but uses memory.
• I don't know why this code works.

sample 20 ms submission

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
        return nil
    } 
    
    pA, pB := headA, headB
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }
        
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    
    return pA
}

sample 23 ms submission & sample 6700 KB submission

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    curA := headA
    curB := headB
    for (curA != curB){
        if curA == nil {
            curA = headB
        } else {
            curA = curA.Next
        }
        
        if curB == nil {
            curB = headA
        } else {
            curB = curB.Next
        }
    }
    return curA
}

sample 24 ms submission

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    	p, q := headA, headB
	for p != q {
		if p == nil {
			p = headB
		} else {
			p = p.Next
		}

		if q == nil {
			q = headA
		} else {
			q = q.Next
		}
	}
	return p
}

sample 25 ms submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenA := linkListLen(headA)
	lenB := linkListLen(headB)

	if lenA == 0 || lenB == 0 {
		return nil
	}

	if lenA > lenB {
		for i := 0; i < lenA - lenB; i++ {
			headA = headA.Next
		}
	} else if lenB > lenA {
		for i := 0; i < lenB - lenA; i++ {
			headB = headB.Next
		}
	}

	for ;headA != nil  && headB != nil; {
		if headA == headB {
			return headA
		}
		headA = headA.Next
		headB = headB.Next
		
	}
	return nil

}

func linkListLen(linkList *ListNode) (ret int) {
	for curr := linkList; curr != nil; curr = curr.Next {
		ret ++
	}
	
	return ret
}

sample 26 ms submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    curr := headA
    Alen := 0
    Blen := 0
    for curr != nil {
        Alen++
        curr = curr.Next
    }
    
    curr = headB
    for curr != nil {
        Blen++
        curr = curr.Next
    }
    
    diff := Alen-Blen
    if Alen > Blen {
        // Bring A list to B list
        for i:=0;i<diff;i++ {
            headA = headA.Next
        }
    } else {
        for i:=0;i<diff*-1;i++ {
            headB = headB.Next
        }
    }
    
    for headA != headB {
        headA = headA.Next
        headB = headB.Next
    }
    
    return headA
}

sample 27 ms submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    
    itA := headA
    itB := headB
    
    for itA != itB {
        if itA != nil {
            itA = itA.Next
        } else {
            itA = headB
        }
        if itB != nil {
            itB = itB.Next
        } else {
            itB = headA
        }
    }
    return itA
}

sample 6400 KB submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    
    listOne := headA
    
    if headA == headB{
        return headA
    }
    
    for {
        if listOne == nil{
            break
        }
         listTwo := headB
        for {
            if listTwo == nil{
                break
            }
            if listOne == listTwo{
                return listOne
            }
            listTwo = listTwo.Next    
        }   
        listOne = listOne.Next
       
    }
    return nil
}

sample 6500 KB submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    listA := headA
    for listA != nil {
        listB := headB
        for listB != nil {
            if listA == listB {
                return listA
            } 
            listB = listB.Next
        }
        listA = listA.Next
    }
    return listA
}

sample 6600 KB submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    
    listOne := headA
    
    if headA == headB{
        return headA
    }
    
    for {
        if listOne == nil{
            break
        }
         // listOne = listOne.Next
         listTwo := headB
        for {
            if listTwo == nil{
                break
            }
            if listOne == listTwo{
                return listOne
            }
            listTwo = listTwo.Next    
        }   
        listOne = listOne.Next
       
    }
    return nil
}

sample 6800 KB submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenHeadA, lenHeadB, newHeadA, newHeadB := 1, 1, headA, headB
	for ref1 := headA; ref1 != nil && ref1.Next != nil; ref1 = ref1.Next {
		lenHeadA++
	}

	for ref2 := headB; ref2 != nil && ref2.Next != nil; ref2 = ref2.Next {
		lenHeadB++
	}
	offset := int(math.Abs(float64(lenHeadA) - float64(lenHeadB)))
	if lenHeadA > lenHeadB {
		for j := 0; j < offset; j, newHeadA = j+1, newHeadA.Next {
		}
	} else {
		for j := 0; j < offset; j, newHeadB = j+1, newHeadB.Next {
		}
	}

	for ; newHeadA.Next != newHeadB.Next; newHeadA, newHeadB = newHeadA.Next, newHeadB.Next {
	}
	if newHeadA == newHeadB {
		return newHeadA
	}

	return newHeadA.Next
}

sample 6900 KB submission

func helper(h1, h2 *ListNode, diff int) *ListNode {
	// Move h1 till the diff
	for i := 0; i < diff; i++ {
		h1 = h1.Next
	}

	// Move both pointer one by one, where they meet is intersection
	for h1 != nil && h2 != nil {
		if h1 == h2 {
			return h1
		}

		h1 = h1.Next
		h2 = h2.Next
	}

	return nil
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	
    if headA == nil || headB == nil {
		return nil
	}

	// Find length of first linkedlist
	var n = 0
	h1 := headA
	for h1 != nil {
		n++
		h1 = h1.Next
	}

	var m = 0
	h2 := headB
	for h2 != nil {
		m++
		h2 = h2.Next
	}

	diff := int(math.Abs(float64(n - m)))

	fmt.Println(n, m)

	if n >= m {
		return helper(headA, headB, diff)
	} else {
		return helper(headB, headA, diff)
	}
}

sample 7000 KB submission

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenx := func(head *ListNode) int {
		n := 0
		for ; head != nil; head = head.Next {
			n++
		}
		return n
	}
	n1, n2 := lenx(headA), lenx(headB)
	if n1 > n2 {
		n1, n2 = n2, n1
		headA, headB = headB, headA
	}
	for i := 0; i < n2-n1; i++ {
		headB = headB.Next
	}
	for i := 0; i < n1; i++ {
		if headA == headB {
			return headA
		}
		headA = headA.Next
		headB = headB.Next
	}
	return nil
}