首页 > itarticle > l234 palindrome linked list

l234 palindrome linked list

admin 11月 13, 2020 0

题目描述

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

解题思路

借助O(n)空间的话，先Linked List的元素转换为数组，然后通过low和high指针判断回文
将Linked List链表进行拆分，对后半部分的链表进行翻转，然后判断其是否相同

Go实现

func (head *ListNode) *ListNode {
    if head.Next == nil {
        return head
    }
    newHead := reverse(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

func isPalindrome(head *ListNode) bool {
    if head == nil{
        return true
    }
    tmp:=head
    n := 0

    for tmp != nil {
        n++
        tmp = tmp.Next
    }

    newHead := head

    if n%2==0 {
        for i:=0;i<=n/2-1 ;i++  {
            newHead = newHead.Next
        }
    }else{
        for i:=0;i<n/2 ;i++  {
            newHead = newHead.Next
        }
    }

    newHead = reverse(newHead)

    for newHead != nil  {
        if head.Val != newHead.Val{
            return false
        }
        head = head.Next
        newHead = newHead.Next
    }
    return true
}