链表算法相关实现

链表反转

go
func reverseList(head *ListNode) *ListNode {
   var prev *ListNode
   curr := head
   for curr != nil {
       next := curr.Next
       curr.Next = prev
       prev = curr
       curr = next
   }
   return prev
}

相交链表

go
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 // 相交节点 or nil

打印链表信息

js
func printListNode(head *ListNode) {
    for head != nil {
        fmt.Printf("%d ->", head->Val)
        head = head.Next
    }
    fmt.Println("nil")
}

创建链表

js
func buildListNode(start, length int) *ListNode {
    dummy := &ListNode{} // 相当于 &ListNode {Val:0, Next: nil} 
    current := dummy // current指针跟踪链表尾部
    for i := 0; i < length; i++ {
        // 在尾部添加新节点
        current.Next = &ListNode{
                Val: start + i,
        }
        current = current.Next // 移动指针到新的尾部
    }

    return dummy.Next
}

链表相关实现测试

golang
// 测试代码
func main() {
    // 构造链表A: 1 -> 2 -> 3 \
    //                         6 -> 7
    //            4 -> 5     /
    // 链表B:          4 -> 5 /
    common := buildListNode(6,2)
    headA := &ListNode{1, &ListNode{2, &ListNode{3, common}}}
    headB := &ListNode{4, &ListNode{5, common}}

    intersection := getIntersectionNode(headA, headB)
    if intersection != nil {
        fmt.Printf("相交节点值: %d\n", intersection.Val)
    } else {
        fmt.Println("没有相交节点")
    }
}