【题目描述】
Implement a function to check if a linked list is a palindrome.
设计一种方式检查一个链表是否为回文链表。
【题目链接】
www.lintcode.com/en/problem/palindrome-linked-list/
【题目解析】
假设一个链表是回文,那么把链表分割为1…n/2,n/2+1…n两个部分,这两个部分肯定是相同的(把第二部分顺序逆转过来或者逆转第一部分)。所以如果我们能把任何一个部分的链表顺序逆转过来,就可以解决这个问题。
那么要怎么逆转过来呢?首先可以用快慢指针得到中间结点(一个指针一次向前移动一个结点,一个移动两个结点),而且在指针移动的同时逆转顺序。
【参考答案】