0234.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]

输出：true

示例 2：

输入：head = [1,2]

输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路

解答

C++JavaScript

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
    ListNode* middle(ListNode* head){
        ListNode* slow= head, *fast =head;
        while(fast && fast->next){
            slow = slow -> next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverse(ListNode* head){
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr!=NULL){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
public:
    bool isPalindrome(ListNode* head) {
        ListNode* mid = middle(head);
        ListNode* head2 = reverse(mid);

        while(head2!=NULL){
            if(head->val != head2->val) return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const reverse = (head) =>{
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

const findhalf = (head) =>{
    let fast = head,slow = head;
    while(fast.next!==null && fast.next.next!==null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;

}
var isPalindrome = function(head) {
    if(head === null)  return true;
    const half = findhalf(head);
    const halflink = reverse(half.next);

    let p1 = head,p2 = halflink,result = true;

    while(result && p2!==null){
        if(p1.val !== p2.val) result = false;
        p1 = p1.next;
        p2 = p2.next;
    }

    half.next = reverse(halflink);
    return result;

};