刷题复习（一）链表
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;
}
}