链表算法相关实现

回文链表判断

• 什么是回文
  • 从两边往中间看，都是相同的 比如121,1221
• 具体实现

golang
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    tail := reverseList(slow.Next)
    p1, p2 := head, tail
    for p2 != nil {
        if p1.Val != p2.Val {
            slow.Next = reverseList(tail)
            return false
        }
        p1 = p1.Next
        p2 = p2.Next
    }
    slow.Next = reverseList(tail)
    return true
}

链表反转

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("没有相交节点")
    }
}