234.回文链表

题目描述

原题
请判断一个链表是否为回文链表。
示例 1:
1
输入: 1->2
2
输出: false
Copied!
示例 2:
1
输入: 1->2->2->1
2
输出: true
Copied!
进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

题解

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public boolean isPalindrome(ListNode head) {
13
//考虑特殊情况
14
if (head == null) {
15
return true;
16
}
17
18
//1.找到前半部分链表的尾节点并反转后半部分链表
19
ListNode firstHalfEnd = endOfFirstHalf(head);
20
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
21
22
//2.判断是否回文
23
ListNode p1 = head;
24
ListNode p2 = secondHalfStart;
25
boolean result = true;
26
//这里p1是从头走的 p2是从一半走的,所以只需要判断p2
27
while (result && p2 != null) {
28
result = p1.val == p2.val;
29
p1 = p1.next;
30
p2 = p2.next;
31
}
32
33
//3.还原链表并返回结果
34
firstHalfEnd.next = reverseList(secondHalfStart);
35
return result;
36
}
37
38
private ListNode reverseList(ListNode head) {
39
ListNode prev = null;
40
ListNode curr = head;
41
while (curr != null) {
42
ListNode next = curr.next;
43
curr.next = prev;
44
prev = curr;
45
curr = next;
46
}
47
return prev;
48
}
49
//类似于找倒数第几个数 这里不过是找中间位置
50
private ListNode endOfFirstHalf(ListNode head) {
51
ListNode fast = head;
52
ListNode slow = head;
53
while (fast.next != null && fast.next.next != null) {
54
fast = fast.next.next;
55
slow = slow.next;
56
}
57
return slow;
58
}
59
}
Copied!
最近更新 3mo ago
复制链接