考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默想起来一个声音:”乔戈里峰”
前言
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
结束语
2018.11.6号 打卡
作者乔戈里亲历2019秋招,哈工大计算机本硕,百度准入职java工程师,欢迎大家关注我的微信公众号:程序员乔戈里。