链表最大孪生和

链表最大孪生和

leetcode 链接

思路：

1.快慢指针找到中间位置

2.将后面的链表进行翻转

3.遍历两个链表，current 和翻转后的链表，计算最大孪生和

go 解法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func pairSum(head *ListNode) int {
    if head == nil {
        return 0
    }
    current := head
    slow := head
    fast := head
    max := 0
    // 找到中点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 翻转后面的节点
    var pre *ListNode
    for slow != nil {
        temp := slow.Next
        slow.Next = pre
        pre = slow
        slow = temp
    }
    // 计算孪生和
    for pre != nil {
        val := pre.Val + current.Val
        if val > max {
            max = val
        }
        pre = pre.Next
        current = current.Next
    }
    return max
}