[leetcode题解]234.Palindrome-Linked-list

leetcode第234题,简单链表操作的题目,题目要求判断给定的单链表是否是回文的,是返回true,否则返回false。

题目比较简单,直接暴力解,通过快慢指针找到中点,然后把前半部分逆置一下,最后把前后向部分判断元素是否依次相等即可,全相等则回文,否则就不是回文。下面用了c++和python同时实现,两者的思路是完全一样的。

c++代码:

class Solution {
public:
    bool isPalindrome(ListNode* head) 
    {
        if (head == NULL || head->next == NULL)return true;
        
        //找中点
        ListNode *fast = head, *slow = head;
        while(fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        bool isOdd = true;
        if (fast->next == NULL)isOdd = false;
        
        if (!isOdd)fast = slow;
        else fast = slow->next;
        
        //将前半部分逆置
        ListNode *pre = new ListNode(-1);
        pre->next = fast;
        slow = head;
        while(slow != fast)
        {
            ListNode *t = slow->next;
            slow->next = pre->next;
            pre->next = slow;
            slow = t;
        }
        
        //前后两部分比较
        slow = pre->next;
        bool isPalindrome = true;
        if (!isOdd)fast = fast->next;
        while(fast != NULL)
        {
            if (slow->val != fast->val)
            {
                isPalindrome = false;
                break;
            }
            slow = slow->next;
            fast = fast->next;
        }
        return isPalindrome;
    }
};

python代码:

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        #找中点
        if head == None or head.next == None:
            return True
        fast = head
        slow = head
        while fast.next != None and fast.next.next != None:
            fast = fast.next.next
            slow = slow.next
            
        isOdd = True
        if fast.next == None:
            isOdd = False
        
        if isOdd:
            fast = slow.next
        else:
            fast = slow
        #前半部分逆置
        pre = ListNode(-1)
        pre.next = fast
        slow = head
        while slow != fast:
            t = slow.next
            slow.next = pre.next
            pre.next = slow
            slow = t
        
        #判断是否是回文
        if not isOdd:
            fast = fast.next
            
        slow = pre.next
        isPalindrome = True
        while fast != None:
            if fast.val != slow.val:
                isPalindrome = False
                break
            fast = fast.next
            slow = slow.next
        return isPalindrome

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]234.Palindrome-Linked-list

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/55.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注