刷题复习（一）链表

https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/

1、合并两个有序链表

思路清晰，双链表有个根节点记录开头

/**
 * 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 ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode root = new ListNode();
        ListNode temp = root;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                temp.next = list2;
                list2 = list2.next;
            } else {
                temp.next = list1;
                list1 = list1.next;
            }
            temp = temp.next;
        }
        if (list1 == null) {
            temp.next = list2;
        } else {
            temp.next = list1;
        }
        return root.next;
    }
}

2、分隔链表

这题需要将链表断开，需要记录表头和表尾

/**
 * 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 {
    //输入：head = [1,4,3,2,5,2], x = 3
    //输出：[1,2,2,4,3,5]
    //示例 2：
    //
    //输入：head = [2,1], x = 2
    //输出：[1,2]

    public ListNode partition(ListNode head, int x) {
        ListNode temp1 = new ListNode();
        ListNode temp2 = new ListNode();
        ListNode root1 = temp1;
        ListNode root2 = temp2;
        while (head != null) {
            if (head.val < x) {
                temp1.next = head;
                temp1 = temp1.next;
            } else {
                temp2.next = head;
                temp2 = temp2.next;
            }
            head = head.next;
        }
        temp1.next = root2.next;
        temp2.next = null;
        return root1.next;
    }

}

3、合并K个升序链表

不难的hard，优先队列 PriorityQueu要学会使用，用优先队列就不难了

        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(o1,o2)->(o1.val-o2.val));

通过lamda方式构造小顶堆，默认就是小顶堆

/**
 * 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 ListNode mergeKLists(ListNode[] lists) {
        if(lists== null ||lists.length== 0){
            return null;
        }
        ListNode root = new ListNode(0);
        ListNode temp = root;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(o1,o2)->(o1.val-o2.val));
        for(ListNode node: lists){
            if(node != null){
                pq.add(node);
            }
        }
        while(!pq.isEmpty()){
            ListNode cur = pq.poll();
            temp.next = cur;
            if(cur.next!=null){
                pq.add(cur.next);
            }
            temp = temp.next;
        }
        return root.next;
    }
}

4、删除链表的倒数第 N 个结点

这道题目有技巧，需要寻找倒数第k个节点

代码应该是如下

// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

完整解答，尤其需要注意测试用例会出现k个数删除倒数第k个，由于算法是寻找倒数k+1的所以需要用虚拟节点root节点去防止出现这种情况

/**
 * 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 ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode root = new ListNode(0);
        root.next= head;
        ListNode cur=help(root,n+1);
        cur.next = cur.next.next;
        return root.next;
    }

    public ListNode help(ListNode head ,int n){
        ListNode temp1 = head;
        for(int i=0;i<n;i++){
            temp1= temp1.next;
        }
        ListNode temp2 = head;
        while(temp1!=null){
            temp2=temp2.next;
            temp1=temp1.next;
        }
        return temp2;
    }
}