Lintcode223 Palindrome Linked List solution 题解
发布在LINTCODE2018年2月22日view:349
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Implement a function to check if a linked list is a palindrome.

设计一种方式检查一个链表是否为回文链表。

【题目链接】

http://www.lintcode.com/en/problem/palindrome-linked-list/

【题目解析】

假设一个链表是回文,那么把链表分割为1…n/2,n/2+1…n两个部分,这两个部分肯定是相同的(把第二部分顺序逆转过来或者逆转第一部分)。所以如果我们能把任何一个部分的链表顺序逆转过来,就可以解决这个问题。

那么要怎么逆转过来呢?首先可以用快慢指针得到中间结点(一个指针一次向前移动一个结点,一个移动两个结点),而且在指针移动的同时逆转顺序。

【参考答案】

http://www.jiuzhang.com/solutions/palindrome-linked-list/

评论
发表评论
暂无评论
PUBLISHED IN

我的收藏