【Leetcode】234.回文链表

234.回文链表

题目：

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

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

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

方法1：用栈

将链表中的节点全部放入一个栈中，由于栈的先进后出的特性，它依次弹出的顺序为链表的逆序。因此，依次比较链表节点和栈弹出的节点，就可以判断链表是否为回文链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isPalindrome(ListNode head) {
    if(head == null)
        return true;
    ListNode cur = head;
    //将链表节点全部入栈
    Stack<ListNode> stack = new Stack<ListNode>();
    while(cur != null){
        stack.push(cur);
        cur = cur.next;
    }
    //依次比较链表节点和栈中弹出节点
    while(!stack.isEmpty()){
        if(head.val != stack.pop().val)
            return false;
        head = head.next;
    }
    return true;
}

时间复杂度：O(n)
空间复杂度：O(n)

方法2:反转链表

彻底不用额外辅助空间的做法：
利用双指针，快指针一次走两步，慢指针一次走一步。快指针走完时，慢指针来到中点。然后将右半部分逆序。最后，一个指针指向链表尾，向前走，遍历右半部分；另一个指针指向链表头，向后走，遍历前半部分。依次比对这两个指
针所指元素是否相同。
注意：题目只让我们判断链表是否回文，我们不能改变题目给我们的结构，所以判断完之后别忘了把链表的指针恢复回来。

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
public boolean isPalindrome(ListNode head) {
    if(head == null)
        return true;
    ListNode fast = head, slow = head;
    //快指针走到末尾，慢指针走到中点
    while(fast.next != null && fast.next.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    //从中点开始，反转后部分链表
    ListNode tail = reverseList(slow);
    ListNode head_cur = head, tail_cur = tail;
    //分别从头和尾开始，比较链表节点
    while(head_cur != null && tail_cur != null){
        if(head_cur.val != tail_cur.val)
            return false;
        head_cur = head_cur.next;
        tail_cur = tail_cur.next;
    }
    //恢复链表
    slow.next = reverseList(tail);
    return true;
    
}
//反转以head为头节点的链表
public ListNode reverseList(ListNode head){
    if(head == null)
        return null;
    ListNode pre = head, cur = pre.next;
    while(cur != null){
        ListNode temp = cur;
        cur = cur.next;
        temp.next = pre;
        pre = temp;
    }
    head.next = null;
    return pre;
}

时间复杂度：O(n)
空间复杂度：O(1)