判断一个链表是否为回文结构
例如:
1
2
3
4
5
| 1 -> 2 -> 1 返回 true
1 -> 3 ->3 -> 1 返回 true
1 -> 2 -> 3 返回 false
|
要求
时间复杂度 O(N) , 空间复杂度 O(1)
题解
若不考虑空间复杂度, 可将所有元素存入栈中, 边出栈边比较即可, 此时空间复杂度为 O(N) ; 也可先 利用快慢指针找到中间指针 , 再将中间指针后的部分存入栈中, 出栈时与链表前半部分比较, 此时空间占用为 N/2 , 空间复杂度仍为 O(N) . 若要实现空间复杂度 O(1) , 可考虑先利用快慢指针找到中间结点, 后将中间结点后的结点的指针方向反向, 即可实现由链表尾向中间结点的遍历, 之后还原链表结构即可. 链表逆序过程中需注意边界, 前半部分最后一个元素和逆序后的后半部分的最后一个元素的 next 均需置空, 否则遍历时很容易死循环.
Java
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class IsPalindrome {
public static ListNode middleNode(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fastPointer = head;
ListNode slowPointer = head;
while (fastPointer != null && fastPointer.next != null) {
fastPointer = fastPointer.next.next;
slowPointer = slowPointer.next;
}
return slowPointer;
}
public static boolean isPalindrome(ListNode head) {
if (head == null)
return true;
ListNode middleNode = middleNode(head);
ListNode tailNode = reversePointer(middleNode);
ListNode leftPointer = head;
ListNode rightPointer = tailNode;
while (leftPointer != null && rightPointer != null) {
if (leftPointer.val != rightPointer.val) {
reversePointer(rightPointer);
return false;
}
leftPointer = leftPointer.next;
rightPointer = rightPointer.next;
}
reversePointer(tailNode);
return true;
}
public static ListNode reversePointer(ListNode startNode) {
ListNode slow = startNode;
ListNode fast = slow.next;
slow.next = null;
ListNode tmp = null;
while (fast != null) {
tmp = fast.next;
fast.next = slow;
slow = fast;
fast = tmp;
}
startNode.next = null;
return slow;
}
}
|
Python
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
| class IsPalindrome:
def middle_node(self, head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
def reverse_pointer(self, start_node):
slow = start_node
fast = start_node.next
slow.next = None
while fast:
tmp = fast.next
fast.next = slow
slow = fast
fast = tmp
start_node.next = None
return slow
def is_palindrome(self, head):
if head is None:
return True
middle_node = self.middle_node(head)
tail_node = self.reverse_pointer(middle_node)
left_pointer = head
right_pointer = tail_node
while left_pointer and right_pointer:
if left_pointer.val != right_pointer.val:
self.reverse_pointer(right_pointer)
return False
left_pointer = left_pointer.next
right_pointer = right_pointer.next
self.reverse_pointer(tail_node)
return True
|