LeetCode 234 回文链表

题目:请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

使用O(n) 时间复杂度和 O(1) 空间复杂度。

  1. 使用快慢指针找到中间位置(偶数的话这里取前一个)
  2. 反转链表
  3. 遍历原始链表和反转链表,比较是否相等。长度不同的话,当较短的比较结束即跳出循环。
  4. (还原链表,题目中没要求,这里就不做了,思路就是再用一遍反转,然后中间结点拼起来)
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
ListNode mid = firstEndOfHalf(head);
ListNode reverse = revList(mid.next);
return cmpList(reverse, head);
}
public ListNode revList(ListNode head){
ListNode prev = null;
ListNode curr = head;
ListNode post = null;
while(curr != null){
post = curr.next;
curr.next = prev;
prev = curr;
curr = post;
}
return prev;
}
public boolean cmpList(ListNode l1, ListNode l2){
while(l1 != null && l2 != null){
if(l1.val != l2.val){
return false;
}
l1 = l1.next;
l2 = l2.next;
}
return true;
}
public ListNode firstEndOfHalf(ListNode head){
if(head == null) return null;
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next!= null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}