讨论/《链表》 - 回文链表/
《链表》 - 回文链表
共 12 个回复
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转链表
        // 节点数量为偶数时,slow是链表中间偏左的节点
        ListNode newHead = reverse(slow.next);
        ListNode p1 = head;
        ListNode p2 = newHead;
        boolean result = true;
        // p2比p1短
        while (result && p2 != null) {
            if (p1.val != p2.val) result = false;
            p1 = p1.next;
            p2 = p2.next;
        }
        slow.next = reverse(newHead);
        return result;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}
2

但是你这样做的话就改变了原来链表的结构了。
得到的结果肯定始终都是truetrue

1

我的思路是把单链表全部反转之后,和原来的链表去做比较,如果一摸一样则为回文链表,方法有些笨,还请大佬给我指点一二

 public boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        ListNode list = null;//定义链式栈的头结点
        if(temp.next == null){//若只有一个元素则返回true,是回文链表
            return true;
        }
        while(temp != null){//头插法反转链表
                ListNode temp1 = new ListNode();//构造新的结点进栈
                temp1.val = temp.val;
                temp1.next = list;
                list = temp1;
                temp = temp.next;
        }
        temp = head;
        //同时遍历两个单链表
        while (temp != null && list != null){
            if(temp.val != list.val){
                return false;
            }
            temp = temp.next;
            list = list.next;
        }
        return true;
    }
1

c++递归

class Solution {
    ListNode *t;
    bool res=true;
public:
    bool recursivelyCheck(ListNode* head)
    {
        if (head==NULL) return true;
        res = recursivelyCheck(head->next)&&(t->val==head->val);
        t=t->next;
        return res;
    }
    bool isPalindrome(ListNode* head) {
        t = head;
        return recursivelyCheck(head);
        
    }
};
1

执行用时:20 ms, 在所有 C++ 提交中击败了85.69%的用户
内存消耗:13.5 MB, 在所有 C++ 提交中击败了91.11%的用户

快慢指针,慢指针走到中间位置,倒置慢指针到尾结点这一段链表。
慢指针从后往前、快指针从前往后依次比较。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *fast,*slow,*rev,*t;
        fast = slow =  head;
        // 快慢指针
        while(fast&&fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast)
            slow = slow->next;
        // 倒置慢指针至尾结点这条链
        reverseList(slow);
        fast = head;
        // slow从尾结点往中间,fast从头结点往中间
        while(slow)
        {
            if(slow->val != fast->val)
                return false;
            slow = slow->next;
            fast = fast->next;
        }
        return true;
    }
private:
    // 倒置链表,参照反转链表
    void reverseList(ListNode* &head)
    {
        ListNode* node = head,*p=NULL,*t;
        while(node)
        {
            t = node;
            node = node->next;
            t->next = p;
            p = t;
        }
        head = p;
    }
};
1

Java递归

class Solution {
    ListNode p;//全局P用于回归时的正序
    public boolean check(ListNode node) {
        if(node==null)return true;//递归出口
        boolean res=check(node.next)&&node.val==p.val;
        p=p.next;
        return res;
    }
    public boolean isPalindrome(ListNode head) {
        p=head;
        return check(head);
    }
}
1

不符合O(1)的空间复杂度

很聪明

Python3

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        """
        思路:1. 找到链表的中间节点 —— 快慢指针
             2. 将后半部分链表反转
             3. 比较链表值
             4. 还原链表
        """
        if not head:
            return True
        # 1. 找到链表前半部分的尾结点
        first_half_end = self.first_half_of_end(head)
        # 2. 对链表后半部分进行反转
        second_half = self.reverse_list(first_half_end.next)
        # 3. 判断是否为回文链表
        result = True
        first_pos = head
        second_pos = second_half
        while result and second_pos is not None:
            if first_pos.val  != second_pos.val:
                return False
            first_pos = first_pos.next
            second_pos = second_pos.next
        # 4. 恢复原链表
        self.reverse_list(second_half)
        return result

    
    # 找到链表前半部分的尾结点
    def first_half_of_end(self, head):
        slow = head
        fast = head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    # 对链表进行反转
    def reverse_list(self, head):
        prev = None
        curr = head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

还原链表