LeetCode-234-Palindrome Linked List

题意:判断一个链表是否是回文链表。

方法一 使用栈

我们先遍历这个链表,然后将他的所有元素压入栈中。由于栈具有后入后出的特性,因此再依次出栈时便刚好是逆序遍历了原来的链表。我们再用一个指针从链表头开始遍历,如果对应的值相等,则说明是回文链表,否则则不是。

方法二 使用栈

和方法一差不多,不同的是只需要将链表的后一半元素进栈就可以了,这样可以省掉一半的空间。

方法三 调整指针指向

原理参见左程云的《程序员代码面试指南》,具体过程如下:
1. 首先改变链表右半区的结构,使整个右半区反转,最后指向中间节点。
2. leftStart和rightStart同时向中间点移动,移动每一步时都比较这两者的值是否相同,如果不同则返回false。
3. 将链表恢复成原样。
4. 返回结果

发表评论

电子邮件地址不会被公开。 必填项已用*标注