Week 49 @ 2024 算法周记【双指针链表】

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lA := getLength(headA)
    lB := getLength(headB)
    
    if lB < lA {
        headA, headB = headB, headA
        lA, lB = lB, lA
    }
    
    for i := 0; i < lB-lA; i++ {
        headB = headB.Next
    }
    
    for headA != headB {
        headA = headA.Next
        headB = headB.Next
    }
    
    return headA
}

func getLength(head *ListNode) int {
    l := 0
    for head != nil {
        l++
        head = head.Next
    }
    return l
}

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