最长回文字符串

实现思路

具体实现

golang
func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    start,end :=0,0
    expand := func(left, right int) (int, int){
        for left >= 0 && right < len(s) && s[left]== s[right]{
            left--
            right++
        }
        return left + 1, right - 1
    }
    for i:=0;i < len(s);i++ {
        left1,right1 := expand(i,i)
        left2,right2 := expand(i,i+1)

        if right1 - left1 > end - start {
            start,end = left1, right1
        }
         if right2 - left2 > end - start {
            start,end = left2, right2
        }
    }
    return s[start:end+1]
}

回文链表

实现思路

• 通过快慢指针，找到中间位置
• 反转后半部分
• 双指针同时移动比对

具体实现

golang
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

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

    return true
}

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

    return prev
}