【力扣234】回文链表

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

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

实现代码

方式一

递归

ListNode p;
public boolean isPalindrome(ListNode head) {

    p = head;
    recursion(head);
    return p.next == null;
}

private ListNode recursion(ListNode head){

    if(head == null) {
        return null;
    }
    ListNode lastNode = recursion(head.next);
    // 在“归”的时候和原链表节点值进行对比
    if(lastNode != null && lastNode.val == p.val){
        p = p.next;
    }
    return head;
}

时间复杂度

时间组成：

假设n个节点

递归到最后一个节点：O(n)
对比一遍：O(n)

总的时间：O(n)

空间复杂度

空间组成：

p变量：O(1)
递归栈：O(n)

总的空间：O(n)

方式二

栈

public boolean isPalindrome(ListNode head) {

    ListNode pp = head;
    // 先将head入栈
    Deque<ListNode> deque = new LinkedList<>();
    while(head != null){
        deque.push(head);
        head = head.next;
    }
    // 取出来
    while (!deque.isEmpty()){
        ListNode pop = deque.pop();
        if(pop.val == pp.val){
            pp = pp.next;
        }
    }
    return pp == null;
}

时间复杂度

时间组成：

入栈时间：O(n)
出栈时间：O(n)

总时间：O(n)

空间复杂度

空间组成：

栈空间：O(n)
变量不记

总空间：O(n)

方式三

快慢指针 + 迭代反转

public boolean isPalindrome(ListNode head) {

    ListNode slow = head, fast = head;
    // slow指针走到中间
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 反转slow之后的节点
    slow = reverse(slow);
    while(slow != null) {
        if(head.val != slow.val){
            return false;
        }
        head = head.next;
        slow = slow.next;
    }
    return true;
}

private ListNode reverse(ListNode head){

    ListNode tmp = null, next;
    while(head != null){
        next = head.next;
        head.next = tmp;
        tmp = head;
        head = next;
    }
    return tmp;
}