📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4764| 回复: 13
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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





上一篇:【LintCode】Binary Tree Maximum Path Sum 修改以后逻辑依然不对
下一篇:为什么同样的代码交多次,所用时间相去甚远?

本帖被以下淘专辑推荐:

推荐
cynthiazp 2015-8-6 04:02:51 | 只看该作者
全局:
  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. *     int val;
  5. *     ListNode *next;
  6. *     ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11.     bool isPalindrome(ListNode* head) {
  12.         
  13.         if (head == nullptr || head->next == nullptr)
  14.             return true;
  15.             
  16.         ListNode* mid = partition(head);
  17.         mid = reverse(mid);
  18.         
  19.         while (head && mid) {
  20.             if (head->val != mid->val)
  21.                 return false;
  22.             
  23.             head = head->next;
  24.             mid = mid->next;
  25.         }
  26.         
  27.         return true;
  28.             
  29.     }

  30. private:
  31.     ListNode* partition(ListNode* head) {
  32.         ListNode* fast = head;
  33.         ListNode* slow = head;
  34.         
  35.         while (fast->next && fast->next->next) {
  36.             fast = fast->next->next;
  37.             slow = slow->next;

  38.         }
  39.         
  40.         fast = slow->next;
  41.         slow->next = nullptr;
  42.         
  43.         return fast;
  44.     }

  45.     ListNode* reverse(ListNode* head) {
  46.         ListNode* prev = nullptr;
  47.         ListNode* curr = head;
  48.         
  49.         while (curr) {
  50.             ListNode* temp = curr->next;
  51.             curr->next = prev;
  52.             prev = curr;
  53.             curr = temp;
  54.         }
  55.         
  56.         return prev;
  57.     }
  58. };
复制代码
这题其实综合性很强,同时考察3道题,Palindrome, reverse Linked List, Middle of LikedList.
题目要求O(1)space, 所以只能是找到中点然后分成两个链表,反转其中一个,再检查Palindrome。
回复

使用道具 举报

全局:
stellari 发表于 2015-8-5 17:46
因为目的不同。List Cycle需要的是找到“同一个node”,Palindrome List需要的是判断“两node是否有相同 ...

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

使用道具 举报

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

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

回复

使用道具 举报

🔗
 楼主| 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是否有相同的值”。
回复

使用道具 举报

全局:
照着这个思路稍作改变就可以了 先把原链表分成长度相当的两部分,然后翻转后一个,最后比较两个链表的值是否相同
回复

使用道具 举报

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

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

使用道具 举报

全局:
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
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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