【leetcode刷题】T109-回文链表

示例 :
输入: ->
输出: false
示例 :
输入: ->->->
输出: true

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True
        # 链表分为前后两部分
        p = head
        q = head
        while q.next and q.next.next:
            p = p.next
            q = q.next.next

        # 后半部分的链表翻转
        head2 = p
        q = p.next
        r = p.next
        while q:
            r = q.next
            q.next = p
            p = q
            q = r

        head2.next = None
        head2 = p

        # 判断是否相等
        p = head
        q = head2
        while p and q:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return True

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 分成前后两部分
        if(!head || !head->next)
            return true;
        ListNode* p = head;
        ListNode* q = head;
        while(q->next && q->next->next){
            p = p->next;
            q = q->next->next;
        }
        // 后部分翻转
        q = p->next;
        ListNode* r = q;
        ListNode* head2 = p;
        while(q){
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        head2->next = NULL;
        head2 = p;

        // 判断是否相同
        p = head;
        q = head2;
        while(p && q){
            if(p->val != q->val)
                return false;
            p = p->next;
            q = q->next;
        }
        return true;
    }
};