回文链表

leetCode–234（回文串）

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

示例 1：

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

示例 2：

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

解法一：自己，使用栈完成

使用栈来存储遍历的链表，后依次出栈，和链表比较。

太低了吧！！ 哈哈哈 加油加油！

代码为：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head==null) return true;
        if (head.next==null) return true;
        if (head.next.next==null && head.val==head.next.val) return true;
        else if (head.next.next==null && head.val!=head.next.val) return false;
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        while (cur!=null){
            if (cur.val!=stack.peek().val) return false;
            else stack.pop();
            cur = cur.next;
        }
        return stack.isEmpty();
    }
}

解法二：双指针

将链表中的元素存储在list集合中，定义两个前后指针，遍历list，对前后指针的元素进行比较。

• 如果是回文链表，则前后指针指向的元素值相等，继续移动 l++,r–。
• 如果前后指针指向的元素不相等，则直接返回false。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //将链表中的值存储到list集合中，通过两个指针进行判断是否是回文链表
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur!=null){
            list.add(cur.val);
            cur = cur.next;
        }
        int l = 0;
        int r = list.size()-1;
        while (l<r){
            if (list.get(l)!=list.get(r)) {
                return false;
            }else {
                l++;
                r--;
            }
        }
        return true;
    }
}

解法三：递归

递归遍历每个节点，前面的那些节点已经在栈中存储了，当到最后一个节点的时候停止，和head元素比较。

通过递归的特性，是由后向前比较，而头结点也依次的向后移动。

算法的正确性在于递归处理节点的顺序是相反的（回顾上面打印的算法），而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。

代码为：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode t;
    public boolean isPalindrome(ListNode head) {
        t = head;
        return check(head);
    }
    public boolean check(ListNode head){
        if (head!=null){
            //首先将指针指到了最后，而t还指向头节点，所以可以进行两两比较
            if (!check(head.next)) return false;  //如果返回false，则直接返回给调用函数的fasle，也就是不是回文链表
            //比较值是否相等，若不相等则直接返回false。
            if (head.val!=t.val) return false;
            t =t.next;
        }
        return true;
    }
}

解法四：快慢指针+链表逆转

使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

将分割后的第二部分进行链表逆转，

比较两个部分的值，当后半部分到达末尾则比较完成。

代码为：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //递归
    public boolean isPalindrome(ListNode head) {
        if (head==null) return true;
        //快慢指针，将链表分成两部分，得到的是第一部分的最后位置
        ListNode first = merge(head);
        //将后半部分进行链表逆转。
        ListNode second = revList(first.next);
        //通过两部分判断是否是回文
        ListNode p1 = head;
        ListNode p2 = second;
        boolean result = true;
        while (result && p2!=null){
            if (p1.val!=p2.val) result =  false;
            p1 = p1.next;
            p2 = p2.next;
        }
        //还原列表，返回结果
        return result;
    }
    //逆转后一部分的链表
    public ListNode revList(ListNode node){
        ListNode pre = null;
        ListNode cur = node;
        ListNode next;
        while (cur!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    //返回分割点
    public ListNode merge(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        //fast.next.next!=null:当链表元素位偶数的时候，fast.next!=null：当链表元素为奇数的时候
        while (fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //当fast到最后，slow正好到第一部分的最后。
        return slow;
    }
}