y******g
发帖数: 254 | 1 知道一个用stack的解法
时间O(n),空间n/2
最优解法是什么？ |
l*****a
发帖数: 14598 | 2 很想知道用stack的解法，展开说说吧
什么时候压栈到头开始popup呢
【在 y******g 的大作中提到】
: 知道一个用stack的解法
: 时间O(n),空间n/2
: 最优解法是什么？
|
l*****a
发帖数: 14598 | 3 难道是两个指针找到中点之后再push?
【在 l*****a 的大作中提到】
: 很想知道用stack的解法，展开说说吧
: 什么时候压栈到头开始popup呢
|
y******g
发帖数: 254 | 4 是用双指针找中点
但是一边找中点的时候就要push了
找到以后开始pop
【在 l*****a 的大作中提到】
: 难道是两个指针找到中点之后再push?
|
p**v
发帖数: 853 | 5 我觉得最好的解法是用recursion的那个，非常elegant，
而且有助于理解recursion。当然，和用stack是一个意思，
但不需要知道中点在哪。
【在 y******g 的大作中提到】
: 知道一个用stack的解法
: 时间O(n),空间n/2
: 最优解法是什么？
|
y******g
发帖数: 254 | 6 在网上搜了一下思路,然后根据思路写了recursive的C++ code
只需要七八行， 确实很简洁
不过我觉得需要在没有干扰的情况下静下心来反反复复想几遍才能想清楚，在面试的时
候，一小会不说话面试官就不耐烦了，这种干扰很大的环境下很难写好这个解法
【在 p**v 的大作中提到】
: 我觉得最好的解法是用recursion的那个，非常elegant，
: 而且有助于理解recursion。当然，和用stack是一个意思，
: 但不需要知道中点在哪。
|
H****r
发帖数: 2801 | 7 如果原linked list 可以修改那O(1)space，O(n) time 即可吧
【在 y******g 的大作中提到】
: 知道一个用stack的解法
: 时间O(n),空间n/2
: 最优解法是什么？
|
b******7
发帖数: 92 | 8 1.找到中间位置
2.将后半部分链表reverse
3.比较两段链表
4.将后半部分链表reverse，还原原链表 |
j**7
发帖数: 143 | 9 public static boolean isPalindrome( Node head)
{
if(head==null)
return false;
int length=0;
Node current=head;
Node end=null;
while(current!=null)
{
length++;
end=current;
current=current.next;
}
int mid=length/2 ;
Node midNode=head;
for(int i=0;i
{
midNode=midNode.next;
}
reverse(midNode);
current=head;
Node right=end;
while(right!=null)
{
if(current.val!=right.val)
{
reverse(end);
return false;
}
current=current.next;
right=right.next;
}
reverse(end);
return true;
}
public static Node reverse(Node head)
{
if(head==null)
return null;
Node current=head;
Node prev=null;
while(current!=null)
{
Node temp=current;
current=current.next;
temp.next=prev;
prev=temp;
}
return prev;
}
public static class Node
{
int val;
Node next;
public Node(int v)
{
val=v;
}
} |
l****i
发帖数: 396 | 10 这个需要知道list的长度吗？
【在 p**v 的大作中提到】
: 我觉得最好的解法是用recursion的那个，非常elegant，
: 而且有助于理解recursion。当然，和用stack是一个意思，
: 但不需要知道中点在哪。
|
l****i
发帖数: 396 | 11 +1
【在 b******7 的大作中提到】
: 1.找到中间位置
: 2.将后半部分链表reverse
: 3.比较两段链表
: 4.将后半部分链表reverse，还原原链表
|
