每天一道leetcode234-回文链表

乔戈里

发布于 2019-09-17 15:09:17

3040

发布于 2019-09-17 15:09:17

文章被收录于专栏：Java那些事

题目

leetcode234-回文链表中文链接： https://leetcode-cn.com/problems/palindrome-linked-list/ 英文链表： https://leetcode.com/problems/palindrome-linked-list/ 难度：easy 分类：链表

题目详述

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2 输出: false 示例 2:

输入: 1->2->2->1 输出: true

题目详解

距离AC只差一个测试用例的错误思路

之前应该有看过关于回文链表的一种解法，就是对于链表的每个元素依次乘以1,2,3,4…求得一个和sum1;
然后就是把这个链表反转，反转链表正好昨天做过哈，每天一道leetcode206-反转链表，直接把代码拿来用，得到反转后的链表;
然后对于这个反转后的链表，依次遍历然后对于每个元素依次乘以1,2,3,4…求得一个和sum2;
然后比较这个两个sum值，如果相等，那么就是回文链表

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        int sum1 = 0;
        if(head == null || head.next == null)
            return true;
        int count = 1;
        ListNode temp = head;
        while(temp != null)
        {
            sum1 += count * temp.val;
            count += 1;
            temp = temp.next;
        }
        int sum2 = 0;
        count = 1;
        head = reverseList(head);
        temp = head;
        while(temp != null)
        {
            sum2 += count * temp.val;
            count += 1;
            temp = temp.next;
        }
        if(sum1 == sum2)
            return true;
        return false;
    }
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode pre = head;
        ListNode pNode = head.next;
        ListNode next = head;
        //首先处理前两个节点；
        pre.next = null;
        while(pNode != null)
        {
            next = pNode.next;
            pNode.next = pre;
            pre = pNode;
            pNode = next;
        }
        return pre;
    }
}

结果，差一个用例没过，说明这种方法还是有点问题~~~~

正确的思路

由于题目说了时间复杂度是O(n),空间复杂度是O(1)，所以不能使用新的空间；
思路还是反转链表，不过不是反转整个链表，反转的是后半部分的链表；
后半部分的链表反转完毕，然后一个从头开始遍历，一个从尾巴开始遍历，依次比较节点的值是不是一样，一样就继续往下，不一样直接就返回false.

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;
        int length = 0;
        ListNode temp = head;
        while(temp != null)
        {
            length++;
            temp = temp.next;
        }
        int halfLength = length / 2;
        temp = head;
        for(int i=0;i<halfLength;i++)
            temp = temp.next;
        ListNode pre = temp;
        ListNode pNode = temp.next;
        ListNode next = pNode;
        while(pNode != null)
        {
            next = pNode.next;
            pNode.next = pre;
            pre = pNode;
            pNode = next;
        }
        for(int i=0;i<halfLength;i++)
        {
            if(head.val != pre.val)
                return false;
            head = head.next;
            pre = pre.next;
        }
        return true;
    }
}