问题是检查给定的链表是否为回文。请告诉我我做错了什么?
The question is to check whether the given linkedlist is palindrome. Please tell what am I doing wrong?
我了解其他方法,例如使用堆栈和反转链表的后半部分。但是,我的方法有什么问题。
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head.next==null){return true;}
while(head!=null){
ListNode ptr=head, preptr=head;
while(ptr.next!=null){ptr=ptr.next;}
if(ptr==head){break;}
while(preptr.next.next!=null){preptr=preptr.next;}
if(head.val==ptr.val){
preptr.next=null;
head=head.next;
}
else{return false;}
}
return true;
}
}```
关于您的解决方案可以说如下:
如果 head
为 null
,则失败并出现异常。为避免这种情况,您可以只删除第一个 if
语句。这种情况不需要单独处理。当列表是单个节点时,第一次迭代将执行 break
,因此您将获得 true
作为 return 值。但至少当 head
是 null
时你不会访问 ->next
它改变了给定的列表。这不是很好。调用者不会预料到会发生这种情况,并且即使在调用 isPalindrome
.
之后也可能需要原始列表用于其他目的
速度很慢。它的时间复杂度是二次的。如果这是编码挑战的一部分,那么测试数据可能会很大,您的函数的执行可能会超过分配的时间。
使用栈确实是一种解决方案,但感觉有点作弊:那你不妨把整个列表转成一个数组,用它的直接寻址能力来测试这个数组是否是回文
您可以只使用列表来执行此操作,如下所示:
- 计算列表中的节点数
- 用它来识别列表后半部分的第一个节点。如果节点数为奇数,则设为中心节点之后的节点。
- 在下半场应用列表反转算法。现在你有两个较短的列表。
- 比较这两个列表中的值是否相等(如果有则忽略中心节点)。记住结果(假或真)
- 重复第 3 步,使反转回滚,列表回到其原始状态。
- Return 在步骤 4 中找到的结果。
这需要线性时间,因此对于更大的列表,这应该优于您的解决方案。
我了解其他方法,例如使用堆栈和反转链表的后半部分。但是,我的方法有什么问题。
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head.next==null){return true;}
while(head!=null){
ListNode ptr=head, preptr=head;
while(ptr.next!=null){ptr=ptr.next;}
if(ptr==head){break;}
while(preptr.next.next!=null){preptr=preptr.next;}
if(head.val==ptr.val){
preptr.next=null;
head=head.next;
}
else{return false;}
}
return true;
}
}```
关于您的解决方案可以说如下:
如果
时你不会访问head
为null
,则失败并出现异常。为避免这种情况,您可以只删除第一个if
语句。这种情况不需要单独处理。当列表是单个节点时,第一次迭代将执行break
,因此您将获得true
作为 return 值。但至少当head
是null
->next
它改变了给定的列表。这不是很好。调用者不会预料到会发生这种情况,并且即使在调用
之后也可能需要原始列表用于其他目的isPalindrome
.速度很慢。它的时间复杂度是二次的。如果这是编码挑战的一部分,那么测试数据可能会很大,您的函数的执行可能会超过分配的时间。
使用栈确实是一种解决方案,但感觉有点作弊:那你不妨把整个列表转成一个数组,用它的直接寻址能力来测试这个数组是否是回文
您可以只使用列表来执行此操作,如下所示:
- 计算列表中的节点数
- 用它来识别列表后半部分的第一个节点。如果节点数为奇数,则设为中心节点之后的节点。
- 在下半场应用列表反转算法。现在你有两个较短的列表。
- 比较这两个列表中的值是否相等(如果有则忽略中心节点)。记住结果(假或真)
- 重复第 3 步,使反转回滚,列表回到其原始状态。
- Return 在步骤 4 中找到的结果。
这需要线性时间,因此对于更大的列表,这应该优于您的解决方案。