zhuguorong 发表于2年前
• 发表于 2年前
• 阅读 2
• 收藏 0
• 评论 0

Given a singly linked list, determine if it is a palindrome.

``````/*
* Given a singly linked list, determine if it is a palindrome.
*
*
* This can be solved by reversing the 2nd half and compare the two halves. Let's start with an example [1, 1, 2, 1].

In the beginning, set two pointers fast and slow starting at the head.

1 -> 1 -> 2 -> 1 -> null
sf
(1) Move: fast pointer goes to the end, and slow goes to the middle.

1 -> 1 -> 2 -> 1 -> null
s          f
(2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.

1 -> 1    null <- 2 <- 1
h                      s
(3) Compare: run the two pointers head and slow together and compare.

1 -> 1    null <- 2 <- 1
h            s
In this end, check if slow == null. For this example, since slow != null, return false.
* */
public class Solution {

public static void main(String[] args) {
// TODO Auto-generated method stub

}
while(fast!=null&&fast.next!=null)
{
fast = fast.next.next;
slow = slow.next;
}
if(fast!=null)//当节点个数为奇数个的时候
slow = slow.next;

//把slow反转
slow = reverseList(slow);

//再与头开始的节点进行比较
//此时slow节点的个数小于等于头节点的个数
{
slow = slow.next;
}
return slow == null;//当slow为null时说明 上一个while中都成立，否则就说明有节点不相等

}
{
}
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x)
{
val = x;
}
}``````

×