234. 回文链表

Posted on | In
Words count in article: 600 | Reading time ≈ 3

题目

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

示例1：

示例1

1
2
输入：head = [1,2,2,1]
输出：true

示例2：

示例2

1
2
输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

进阶

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

解法

解法一：

借助数组

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isPalindrome(ListNode head) {
		ArrayList<Integer> nums = new ArrayList<>();
		while (head != null) {
			nums.add(head.val);
			head = head.next;
		}
		
		int begin = 0;
		int end = nums.size() - 1;
		while (begin < end) {
			if (nums.get(begin).intValue() != nums.get(end).intValue()) {
				return false;
			}
			begin++;
			end--;
		}
		return true;
    }

这里要注意一个点，之前第11行的比较语句是nums.get(begin) != nums.get(end)，在跑以下测试用例的时候是没有问题的。

[1,2]
[1,2,1]
[1,2,2,1]

但是碰到用例[-129,-129]就出现解答错误。然后才想起来，JVM对整型数据有优化，[-128,128]范围内的数字是共享的，所以一旦数字超过范围nums.get(begin) != nums.get(end) 就不会再相等了。

这才把比较语句改为nums.get(begin).intValue() != nums.get(end).intValue()

解法二：

借助栈和快慢指针

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        Stack<ListNode> stack = new Stack<>();
        while(fast != null && fast.next != null){
            stack.push(slow);
            fast = fast.next.next;
            slow = slow.next;
        }
        
        if(fast != null){
            slow = slow.next;
        }
        while(slow != null){
            if(stack.pop().val != slow.val) return false;
            slow = slow.next;
        }
        return true;
    }

解法三：

快慢指针和翻转链表

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
public boolean isPalindrome(ListNode head) {
        if(head==null)return true;//处理输入为空的情况，返回true
        ListNode slow = findMid(head);
        if(head==slow){//处理只有一个或两个节点的情况
            if(head.next==null||head.val==head.next.val)return true;
            else return false;
        }
        reverse(slow);//反转链表的后半部分
        boolean result = compare(head,slow.next);
        reverse(slow);//恢复链表原本的结构
        return result;
    }
    public ListNode findMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
    public void reverse(ListNode slow){ //链表就地反转 参考：https://www.cnblogs.com/mwl523/p/10749144.html
        ListNode pre = slow.next;
        ListNode pCur = pre.next;
        while(pCur!=null){
            pre.next=pCur.next;
            pCur.next=slow.next;
            slow.next=pCur;
            pCur=pre.next;
        }
    }
    public boolean compare(ListNode one,ListNode two){//比较两部分链表是否相同
        while(one!=null&&two!=null){
            if(one.val!=two.val)return false;
            one=one.next;
            two=two.next;
        }
        return true;
    }
0%