题目
请判断一个链表是否为回文链表。
示例 1:
示例 2:
进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路
这道题,有上中下三种解法:
下等解法,直接用个栈来存储每个链表的元素,由于栈是后进先出的,所以每一个出栈元素都是链表的末尾元素,这时候可以直接和头元素比较是否相等.
但是这样做的缺点很明显,首先浪费时间和空间;其次要是这个链表是循环链表,那就爆栈了.
中等解法,将链表整条直接反转,然后继续比较两条链表是否完全一致.
这样做的缺点是,会浪费一点点的时间,因为我们知道,如果一条链是回文链,那其实只要比较一半的数据就够了,并不需要完全比较.
上等解法,找到链表的中点,然后将中点节点的后面部分反转,如果和前面部分一致,那就说明是回文链表了.
而反转链表的这个部分,可以直接找回当初的206.反转链表.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public bool IsPalindrome(ListNode head)
{
if (head == null || head.next == null)
{
return true;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null)
{
fast = fast.next.next;//快的每次走两步.
slow = slow.next;//慢的每次走一步,快的走到尾了,慢的就会在中间.
}
ListNode newLinkedList = null;//创建一个新的链表.
while (slow != null)
{
ListNode tempNode = slow.next;//创建临时链表存放头节点的尾巴.
slow.next = newLinkedList;//将新链表接到头节点后面.
newLinkedList = slow;//再次成为新链表.
slow = tempNode;//将临时链表覆盖原链表.
}
slow = newLinkedList;
while (slow != null)
{
if (slow.val != head.val)
{
return false;
}
slow = slow.next;
head = head.next;
}
return true;
}
|