每天一道leetcode234-回文链表

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

内容简介:考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默想起来一个声音:”乔戈里峰”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-回文链表》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

The Facebook Effect

The Facebook Effect

David Kirkpatrick / Simon & Schuster / 2010-6-8 / USD 26.00

《Facebook 效应》的作者近距离地采访了与Facebook相关的人士,其中包括Facebook的创始人、员工、投资人、意向投资人以及合作伙伴,加起来超过了130人。这是真切详实的访谈,更是超级精彩的故事。作者以其细腻的笔触,精巧的叙事结构,解密了Facebook如何从哈佛的宿舍里萌发,创始人的内讧,权力之争,如何放弃华盛顿邮报的投资,怎样争取到第一个广告客户,而第一轮融资又如何获得一亿美元的......一起来看看 《The Facebook Effect》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

随机密码生成器
随机密码生成器

多种字符组合密码

URL 编码/解码
URL 编码/解码

URL 编码/解码