234. 回文链表

很有代表性！包含了链表遍历，快慢指针找中点模版，链表数据比对，链表反转！非常具有代表性

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        // 找中点 1=>1 123=>2 1234=>2
        ListNode A_end = mid(head);
        ListNode B_start = A_end.next;
        A_end.next = null;
        // 翻转后半部分
        B_start = reverse(B_start);
        // 比对
        boolean res = compare(head, B_start);
        // 还原
        A_end.next = reverse(B_start);
        return res;
    }
    // 链表找中点，快慢指针法
    ListNode mid(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while(q.next != null && q.next.next != null) {
            p = p.next;
            q = q.next.next;
        }
        return p;
    }
    // 链表反转模板
    ListNode reverse(ListNode head) { // 三人行模板
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next; // 松手先保存
            cur.next = pre;
            pre = cur; // 归位
            cur = temp;
        }
        return pre;
    }
    // 链表比对模板(len(B) <= len(A))
    boolean compare(ListNode A, ListNode B) {
        while(B != null) {
            if(A.val != B.val) return false;
            A = A.next;
            B = B.next;
        }
        return true;
    }
}

23. 合并K个升序链表

难度困难

合并两个链表不难 创造一个虚拟头结点从小到达连接结点而已！关键在于如何找到小结点，一一对比就可以，但是多个链表就得把每条练表排序，找到小结点，这时候就需要一个排序队列PriorityQueue

PriorityQueue<ListNode> pd = new Priority<>(length,(a,b)->(a.val - b.val))
    第一个参数是队列长度，第二个是排序规则：对数器

所以答案如下：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0){
            return null;
        }
        //吧链表存放在一个排序队列里面
            // 优先级队列，最小堆
       PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
        //PriorityQueue pq = new PriorityQueue<>(lists.length,(a,b)->(a.val - b.val));
        for(ListNode list : lists){
            if(list != null){
                 pq.add(list);
            }  
        }
        //定以一个虚拟结点
        ListNode dummy = new ListNode();
        //头结点不能移动
        ListNode p = dummy;
        while(!pq.isEmpty()){
            ListNode temp = pq.poll();
            p.next = temp;
            if(temp.next != null){
                pq.add(temp.next);
            }
            p = p.next;
        }
        return dummy.next;
    }
}

141. 环形链表

判断链表是否有环，快慢双指针，一个走两步，一个走一步总会相遇，相遇的时候快指针比慢支针多走一圈环的距离，

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //注意这里是&&，两个条件都得满足
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

那么如何找到相交的第一个结点呢？找到相等的结点后让慢支针回到头结点，快指针停在原地，两者同时走一步，第一次相遇的点就是入环结点；

 //注意这里是&&，两个条件都得满足
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                //在这找入环结点
                //慢指针回到头借点位置
                slow = head;
                //两者同时走一步
                while(slow != fast){
					slow = slow.next;
                    fast = fast.next;
                }
                //之后就是头借点位置！
                return slow;
            }
        }

19. 删除链表的倒数第 N 个结点

关键在于如何找到倒数的第n个结点！利用快慢指针先走n步，再同时走一步！慢指针最后到达的位置就是倒数第n个结点
删掉就简单
但是：如果删除的是第一个结点怎么办？
这就需要添加一个虚拟头结点！

 /*
 关键在于如何找到倒数的第n个结点！利用快慢指针先走n步，再同时走一步！慢指针最后到达的位置就是倒数第n个结点
 删掉就简单
 但是：如果删除的是第一个结点怎么办？
 这就需要添加一个虚拟头结点！
  */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
            //找到这个结点，快慢指针
            ListNode fast = new ListNode(0,head);
            ListNode slow = new ListNode(0,head);
            ListNode dummy = slow;
            while(n > 0){
                fast = fast.next;
                n--;
            }
            while(fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return dummy.next;
    }
}

92. 反转链表 II

典中典！反转整个链表倒是很简单！

ListNode reverse(ListNode head){
    if(head.next == null){
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

• 反转前n个也简单！basecase换一下不用走到最后就好了

ListNode reverse(ListNode head,int n){
    if(n == 1){
        //需要记录一下后驱结点
        houqu = head.next;
        return head;
    }
    ListNode last = reverse(head.next,n-1);
    head.next.next = head;
    head.next = houqu;
    return last;
}

• 那么重点来了！反转链表中的一部分怎么办？
• 学会转换，把不会的转换成会的，我们会反转前n个，就把他转换成前n个的问题不就好了，那就是用递归把左边开始位置变成1，

ListNode reverseBetwen(ListNode head, int left, int right){
    if(left == 1){
        //反转
        return reverse(head, right);
    }
    //接起来
    head.next = reverseBetwen(head.next,left - 1, right -1);
    return head;
}

25. K 个一组翻转链表

反转前k个很简单、需要记录后驱结点，但这不只有前k个，有多个前k个；
需要两个结点记录需要反转的链表的起点和终点，a,b
把a当起点，反转[a,b)链表！
在以b为起点当成另一个组递归，又会产生一个[a,b）
把第一个a接到第二个反转后的结点上！

 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode a = head,b = head;
        //判断是否足够反转
        for(int i = 0; i < k; i++){
            if(b == null){
                return head;
            }
            b = b.next;
        }
        //足够就反转[a,b)
        ListNode newNode = reverseK(a,b);
        //连接结点
        a.next = reverseKGroup(b,k);
        return newNode;
    }
    //反转区间结点
    ListNode reverseK(ListNode a, ListNode b){
        if(a.next == b){
            return a;
        }
        ListNode last = reverseK(a.next, b);
        a.next.next = a;
        a.next = null;
        return last;
    }
}