LeetCode 234.回文链表-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目：给定一个单链表的头节点，要求判断该链表是否为回文链表。如果是的话就返回true，否则返回false。

解题思路

回文我们之前已经见过很多次了，例如字符串abba以及chjjhc等等，通俗来说就是正着读反着读都一样的就是回文。那么我们复习一下判断一个字符串是不是回文字符串：

一个简单的思路就是我们可以同时从字符串的首元素和尾元素进行从前往后和从后往前的遍历，每次遍历都检查元素是否相同，当遇到不相同的就直接返回false，否则就是true。
另一种思路就是依靠栈来存储字符，具体来说首先遍历字符串，依次将字符元素入栈，此时栈中就装满了和字符串等长的字符。此时再次遍历字符串，在遍历的同时出栈，比较两个元素是否相等。

那么回到本题，本题所面临的是一个链表结构，无法向字符串一样可以从后往前遍历。简单的思路就是将字符串反转，之后同时遍历两个链表检查对应元素不久ok了，看下面代码：

// 反转整个链表则破环了原链表的head
public boolean isPalindrome(ListNode head) {
    ListNode reverse = new ListNode(-1);
    ListNode cur = head;
    while(cur!=null){
        ListNode temp = cur.next;
        cur.next = reverse.next;
        reverse.next = cur;
        cur = temp;
    }
    cur = reverse.next;
    while(head!=null&&cur!=null){
        if(head.val!=cur.val) return false;
        head = head.next;
        cur = cur.next;
    }
    return true;
}
复制代码

上面的思路是没问题的，问题出现在反转的时候在原链表上进行反转，破坏了原始链表的结构，正确的做法是每次都新建一个结点，将原始结点进行赋值即可，如下：

// 反转整个链表必须创建新的结点
public  boolean isPalindrome2(ListNode head) {
    ListNode reverse = new ListNode(-1);
    ListNode cur = head;
    while(cur!=null){
        ListNode curNode = new ListNode(cur.val);
        curNode.next = reverse.next;
        reverse.next = curNode;
        cur = cur.next;
    }
    cur = reverse.next;
    while(head!=null&&cur!=null){
        if(head.val!=cur.val) return false;
        head = head.next;
        cur = cur.next;
    }
    return true;
}
复制代码

此代码最终耗时6ms，时间复杂度和空间复杂度都是 $O(n)$ 。题目的要求是使用时间复杂度 $O(n)$ ，空间复杂度为 $O(1)$ 的算法，那么根据上面的思路有没有可能进行优化呢？答案是肯定的，我们最终要判断的无非就是将第一个结点和最后一个结点进行比较，将第二个和倒数第二个比较，以此类推。

那么我们是不是只需要将链表的前半截和链表的后半截反转进行比对即可，我们可以用快慢指针来获取链表的中点，之后进行原地反转和循环判断即可，代码如下：

// 双指针找到中心结点，反转后部分
public boolean isPalindrome3(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while(fast.next!=null&&fast.next.next!=null){
        fast = fast.next.next;
        slow = slow.next;
    }
    ListNode reverse = new ListNode(-1);
    ListNode cur = slow.next; // attention here
    while(cur!=null){
        ListNode temp = cur.next;
        cur.next = reverse.next;
        reverse.next = cur;
        cur = temp;
    }
    cur = reverse.next;
    while(cur!=null){ // attention here
        if(head.val!=cur.val) return false;
        head = head.next;
        cur = cur.next;
    }
    return true;
}
复制代码