内容简介:考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默想起来一个声音:”乔戈里峰”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; } } 复制代码
结果,差一个用例没过,说明这种方法还是有点问题~~~~
正确的思路
- 由于题目说了时间复杂度是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-回文链表》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 每日一道 LeetCode (3):回文数
- 回文算法(JavaScript)
- 让我们一起啃算法----回文数
- java算法题:最长回文串
- 判断单链表回文的三种方法
- leetcode刷题(python解题)-----9.回文数
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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》 这本书的介绍吧!