每天一道leetcode234-回文链表

栏目: 数据库 · 发布时间: 5年前

内容简介:考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默想起来一个声音:”乔戈里峰”2018.11.6号打卡明天的题目:

考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默想起来一个声音:”乔戈里峰”

前言

2018.11.6号打卡

明天的题目: leetcode-cn.com/problems/re… 以后明天的题目提取公布一下哈,因为有些朋友想提前做一下~

题目

leetcode234-回文链表 中文链接: leetcode-cn.com/problems/pa… 英文链表: leetcode.com/problems/pa… 难度:easy 分类:链表

题目详述

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

示例 1:

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

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

题目详解

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

  • 之前应该有看过关于回文链表的一种解法,就是对于链表的每个元素依次乘以1,2,3,4...求得一个和sum1;
  • 然后就是把这个链表反转,反转链表正好昨天做过哈,直接把代码拿来用,得到反转后的链表;
  • 然后对于这个反转后的链表,依次遍历然后对于每个元素依次乘以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;
    }
}
复制代码

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

每天一道leetcode234-回文链表

正确的思路

  • 由于题目说了时间复杂度是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;
    }
}
复制代码

代码讲解

  • 15到20行,遍历链表,求链表长度的一半的值
  • 22-23行,找到链表的中间节点
  • 24-33行反转链表
  • 34-40行一个从头,一个从尾巴,依次比较值是否相等,不相等就返回false
  • 最后就是返回true

以上所述就是小编给大家介绍的《每天一道leetcode234-回文链表》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

How to Design Programs

How to Design Programs

Matthias Felleisen、Robert Bruce Findler、Matthew Flatt、Shriram Krishnamurthi / The MIT Press / 2001-2-12 / 71.00美元

This introduction to programming places computer science in the core of a liberal arts education. Unlike other introductory books, it focuses on the program design process. This approach fosters a var......一起来看看 《How to Design Programs》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具