avatar

day11_234_回文链表

题目

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

示例 1:

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

示例 2:

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

进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

Related Topics

  • 链表
  • 双指针

解答

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
66
67
68
69
70
71
72
73
74
75
//请判断一个链表是否为回文链表。 
//
// 示例 1:
//
// 输入: 1->2
//输出: false
//
// 示例 2:
//
// 输入: 1->2->2->1
//输出: true
//
//
// 进阶:
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
// Related Topics 链表 双指针


//leetcode submit region begin(Prohibit modification and deletion)
/**
* 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 || head.next == null) return true;

//第一遍遍历链表记录其长度
int length = 0;

ListNode previous = head;
while(previous != null){
length++;
previous = previous.next;
}

//第二次遍历链表。此时已经得到了链表的长度,将链表中的元素移动到数组中
int[] arr = new int[length];
int index= 0;
while(head != null){
arr[index] = head.val;
index++;
head = head.next;
}

//此时已经得到数组,也即将问题转化为判断数组中的元素是否为回文。
//双指针法判断是否为回文。
int after = arr.length / 2;
int before = after - 1;

if(arr.length % 2 == 1){
//奇数个元素
after++;
}

while(before >= 0 || after < arr.length){
if(arr[before] == arr[after]){
before--;
after++;
}else{
return false;
}
}

return true;
}


}
//leetcode submit region end(Prohibit modification and deletion)
文章作者: 无知的小狼
文章链接: https://bytedance.press/2020/05/05/20200501/day11_234_%E5%9B%9E%E6%96%87%E9%93%BE%E8%A1%A8/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 无知的小狼

评论