一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1556|回复: 13
收起左侧

[树/链表/图] Palindrome Linked List 求助

[复制链接] |试试Instant~ |关注本帖
oio14644 发表于 2015-8-5 15:40:15 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x

思路是先翻转整个链表,然后和之前的链表比较,能部分通过,不知道问题出在哪里?

还有 head.val!=reverse.val  和 head!=reverse,有什么不同?

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) {
                        return true;
                }
                ListNode reverse = reverse(head);
                while (head!=null&&reverse!=null) {
                        if (head.val!=reverse.val) {
                                return false;
                        }
                        head=head.next;
                        reverse=reverse.next;
                }
                return true;
        }

        private ListNode reverse(ListNode head) {
                if (head==null) {
                        return null;
                }
                ListNode dummy = new ListNode(-1);
                dummy.next= head;
                ListNode pre = dummy.next;
                ListNode cur = pre.next;
                while (cur!=null) {
                        pre.next=cur.next;
                        cur.next=dummy.next;
                        dummy.next=cur;
                        cur=pre.next;
                }
               
                return dummy.next;
        }
}



Submission Details
14 / 21 test cases passed.
Status: Wrong Answer
Submitted: 3 minutes ago

Input:[1,1,2,1]
Output:true
Expected:false




本帖被以下淘专辑推荐:

stellari 发表于 2015-8-5 17:44:14 | 显示全部楼层
“先翻转整个链表,然后和之前的链表比较”听起来是可行的,但是当你“翻转了整个链表”以后,“之前的链表”已经不存在了啊。这时候的head其实是指向翻转后的链表的最后一个元素,所以这段代码的本质是:“比较链表的第1个和最后1个元素是否相同”。

如果用这个思路的话,你就必须创建一个原始链表的备份才行。但与其那样做,还不如干脆把List中元素拷贝到数组中算了,因为都是O(N)内存,后者实现起来还简单快捷一些。

回复 支持 1 反对 0

使用道具 举报

小A要当码农 发表于 2015-8-5 22:37:26 | 显示全部楼层
stellari 发表于 2015-8-5 17:46
因为目的不同。List Cycle需要的是找到“同一个node”,Palindrome List需要的是判断“两node是否有相同 ...

求问大神,我的思路和你一样,拷贝链表中的各个val到数组,然后对数组进行检验(首递减,尾递增),但是这样虽然时间复杂度好像是O(n),但是空间复杂度并没有达到题目的要求0(1)呀,而是O(n)...
回复 支持 0 反对 1

使用道具 举报

 楼主| oio14644 发表于 2015-8-5 15:40:31 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2015-8-5 15:56:23 | 显示全部楼层
那为什么循环链表那到题目能直接比较node,而不是比较node的val
* Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
* 一道比较出名的面试题,思路是用一个快指针,一个慢指针。快指针每次向前进两步,慢指针每次向前进一步。
* 如果链表有环的话,快指针因为没法到达链表尽头迟早会和慢指针相遇,因此如果在到达链表尽头前两者相遇就表示链表有环路。
*/
public class LinkedListCycle {
        public boolean hasCycle(ListNode head) {
                ListNode slow = head;
                ListNode fast = head;
                while (fast != null && fast.next != null) {
                        fast = fast.next.next;
                        slow = slow.next;
                        if (slow == fast) {
                                return true;
                        }
                }
                return false;
        }
}
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-5 17:46:02 | 显示全部楼层
oio14644 发表于 2015-8-5 15:56
那为什么循环链表那到题目能直接比较node,而不是比较node的val
* Given a linked list, determine if it  ...

因为目的不同。List Cycle需要的是找到“同一个node”,Palindrome List需要的是判断“两node是否有相同的值”。
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-8-5 23:15:01 | 显示全部楼层
照着这个思路稍作改变就可以了 先把原链表分成长度相当的两部分,然后翻转后一个,最后比较两个链表的值是否相同
回复 支持 反对

使用道具 举报

头像被屏蔽
cynthiazp 发表于 2015-8-6 04:02:51 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| oio14644 发表于 2015-8-6 04:28:22 | 显示全部楼层
cynthiazp 发表于 2015-8-6 04:02
这题其实综合性很强,同时考察3道题,Palindrome, reverse Linked List, Middle of LikedList.
题目要求O ...

你写的这个是O(1) 的空间吗?
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-8-6 10:46:35 | 显示全部楼层
cynthiazp 发表于 2015-8-6 04:02
这题其实综合性很强,同时考察3道题,Palindrome, reverse Linked List, Middle of LikedList.
题目要求O ...

同样的思路用python写了遍。另外觉得您的code可以AC但是似乎有点小瑕疵 在第十九行应该是while(mid),因为您的patition function对奇数长度的链表是不能分成长度相等的两部分的,后半部分的链表要比前一个短一个,所以翻转后应该以后一个较短链表为准 这样可以忽略掉原链表前一部分长出来的那一个node 您这样partition确实比较简洁一点
  1. class Solution:
  2.     def isPalindrome(self, head):
  3.         if head is None or head.next is None:
  4.             return True
  5.         slow=head
  6.         fast=head.next
  7.         while fast is not None and \
  8.             fast.next is not None and\
  9.             fast.next.next is not None:
  10.             slow=slow.next
  11.             fast=fast.next.next
  12.         if fast.next is None:
  13.             second=slow.next
  14.             slow.next=None
  15.         else:
  16.             second=slow.next.next
  17.             slow.next=None
  18.         second=self.reverse(second);
  19.         while head is not None:
  20.             if head.val != second.val:
  21.                 return False
  22.             second=second.next
  23.             head=head.next
  24.         return True
  25.             
  26.     def reverse(self,head):
  27.         if head is None or head.next is None:
  28.             return head
  29.         newHead=head
  30.         while head.next is not None:
  31.             next=head.next.next
  32.             head.next.next=newHead
  33.             newHead=head.next
  34.             head.next=next
  35.         return newHead
复制代码
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-15 23:29:35 | 显示全部楼层
oio14644 发表于 2015-8-6 04:28
你写的这个是O(1) 的空间吗?

这个是O(1),你还有啥问题吗这个题?
回复 支持 反对

使用道具 举报

自己人 发表于 2016-7-31 10:01:37 | 显示全部楼层
stellari 发表于 2015-8-5 17:44
“先翻转整个链表,然后和之前的链表比较”听起来是可行的,但是当你“翻转了整个链表”以后,“之前的链表 ...

不用啊,定义几个新的节点指向head和head->next,这样不是没改变原本的链表吗?head还是正向的啊
回复 支持 反对

使用道具 举报

自己人 发表于 2016-7-31 10:06:48 | 显示全部楼层
楼主,我也是用同样的方法,怎么都通不过,请问你最后怎么解决的
回复 支持 反对

使用道具 举报

OO0OO 发表于 2016-8-10 23:22:39 | 显示全部楼层
自己人 发表于 2016-7-31 10:06
楼主,我也是用同样的方法,怎么都通不过,请问你最后怎么解决的

引用一下:
“先翻转整个链表,然后和之前的链表比较”听起来是可行的,但是当你“翻转了整个链表”以后,“之前的链表”已经不存在了啊。这时候的head其实是指向翻转后的链表的最后一个元素,所以这段代码的本质是:“比较链表的第1个和最后1个元素是否相同”。



如果用这个思路的话,你就必须创建一个原始链表的备份才行。但与其那样做,还不如干脆把List中元素拷贝到数组中算了,因为都是O(N)内存,后者实现起来还简单快捷一些。


你不能只定义指向head和head.next,如果你要定义,就要做原链表的拷贝,因为你后来翻转链表的时候会改变本身的链表,建议可以打印一下原本的linkedlist看看是否结构依旧正确。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表