笔记 | 单链表回文序列判断

方法一（栈法）：

1.新建一个栈用于存储链表的数据，注意如果存储节点栈的类型为 LinkNode ，存储 .val 数据类型为 Integer。

2.设置头指针 cur 遍历链表直到 cur 为空，每次将链表数据压入栈中

3.重新设置头指针 prev ，根据链表先进后出的特性，每次取栈顶元素与链表元素进行比较，同时 prev后移一位

注解：同理该方法可以将元素用数组存储

import java.util.*;

public class Solution {
    //main函数，测试使用
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        boolean flag = isPail(listNodeAdd(listNode));
        System.out.println(flag);
    }
  
    //简单的构造一个链表{1, 2, 1}用于测试
    public static ListNode listNodeAdd(ListNode next) {
        ListNode node = new ListNode(2);
        next.next = node;
        ListNode node1 = new ListNode(1);
        next.next.next = node1;
        return next;
    }
  
    //头结点类，同时也是节点类（可以这么理解）
    public static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            val = this.val;
            next = null;
        }
    }
    /**
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public static boolean isPail (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return ture;
        }
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        ListNode prev = head;
        for (int i = 0; i < stack.size(); i++) {
            if (stack.pop() == prev.val) {
                prev = prev.next;
            } else {
                return false;
            }
         }
        return true;
     }
}

时间复杂度：O(n)

空间复杂度：O(n)

方法二（快慢指针+链表逆置）：

1.快慢指针找中点：先使用快慢指针找到链表的中点，然后根据中点找到表示后半段链表的头节点。

>可以利用 快慢指针，快指针一次走两步，慢指针依次走一步，当快指针走到终点的时候，此时如果链表的长度为偶数时，此时中 >间节点有两个，慢指针则走到了中间两个左边那个。反之，如果链表长度为奇数时，则慢指针走到中间节点。

2.反转链表：反转慢指针的下一个节点（无论链表个数是奇数还是偶数都满足我们的目标）

3.遍历比较：指针前移依次比较直到节点为空或者节点值不相等为止

    public boolean isPail (ListNode head) {
        if (head == null || head.next == null)
            return true;
        ListNode fast = head;
        ListNode slow = head;
        while (slow.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode reverseHead = reverseList(slow.next);

        while (head != null && reverseHead != null) {
            if (head.val != reverseHead.val)
                return false;
            head = head.next;
            reverseHead = reverseHead.next;
        }
        return true;
    }

    //链表逆置操作
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode prev = null;
        ListNode flag = head.next;//记录head的下一个位置
        while (head != null) {
            head.next = prev;
            prev = head;
            head = flag;
        }
        return flag;
    }

时间复杂度：O(n)

空间复杂度：O(1)

END：其他方法基本都是上面方法的变形