234. 回文链表

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

解题思路

解法1：
1.对链表进行遍历，转换为字符串
2.对字符串采用双指针遍历方法（两个指针，一个从前往后，一个从后往前），判断是否为回文字符串
此解法，时间复杂度是O（n）,空间复杂度是O（n）
运行效率为：

解法1运行效率

解法2：
1.翻转链表
2.遍历对比翻转链表和输入链表，判断值是否相等
此解法，时间复杂度是O（n）,空间复杂度是O（n）
运行效率为：

解法2运行效率

解题遇到的问题

1.翻转链表，可以使用哑结点的方法
中心思想是：
1）创建哑结点new ListNode(0);
2）遍历head，每次遍历，将哑结点的next先保存下来
3）将哑结点的next指向目前遍历到的head值的节点
4）再将这次遍历临时保存下来的哑结点的next节点，重新连接到哑结点的m.next.next = temp
5）直到head为null，遍历完成，m.next即为翻转后的链表
模版代码为：

/**
     * 翻转链表 
     */
    public ListNode revListNode(ListNode head) {
        ListNode m = new ListNode(0);
        ListNode temp = null;
        while (head != null) {
            temp = m.next;
            m.next = new ListNode(head.val);
            head = head.next;
            m.next.next = temp;
        }
        return m.next;
    }

2.求取链表中的倒数节点，可以使用快慢指针的方法
中心思想是：
1）双指针移动，初始都指向head
2）先将p1移动k位
3）然后才开始移动p2，同时继续移动p1
4）直到p1指向末尾，那么p2将会移动L-k个位置，那么p2此时指向为倒数第k个节点
模版代码为：

    /**
     * 快慢指针找到链表的倒数k节点
     */
    public ListNode getNthKNode(ListNode head, int k) {
        ListNode p1 = head, p2 = head;
        while (p1 != null) {
            p1 = p1.next;
            if (k < 1) {
                p2 = p2.next;
            }
            k--;
        }
        return p2;
    }

后续需要总结学习的知识点

无

##解法1
class Solution {
    public boolean isPalindrome(ListNode head) {
        StringBuilder builder = new StringBuilder();
        while (head != null) {
            builder.append(head.val);
            head = head.next;
        }
        int l = 0, r = builder.length() - 1;
        while (l < r) {
            if (builder.charAt(l) != builder.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    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;
        }
    }
}

##解法2
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode reListNode = revListNode(head);
        while (head != null || reListNode != null) {
            System.out.println(head.val + "  " + reListNode.val);
            if (head.val != reListNode.val) {
                return false;
            }
            head = head.next;
            reListNode = reListNode.next;
        }
        return true;
    }

    /**
     * 翻转链表 
     */
    public ListNode revListNode(ListNode head) {
        ListNode m = new ListNode(0);
        ListNode temp = null;
        while (head != null) {
            temp = m.next;
            m.next = new ListNode(head.val);
            head = head.next;
            m.next.next = temp;
        }
        return m.next;
    }
    /**
     * 快慢指针找到链表的中间节点
     */
    public ListNode getMidNode(ListNode head) {
        ListNode p1 = head, p2 = head;
        while (p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    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;
        }
    }
}