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; }
}
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头节点
例子：
1 -> 2 -> 3 -> 4 -> 5
1 -> 2 -> 3 -> 5
输入1：
head = [1,2,3,4,5] , n = 2;
输出1：
[1,2,3,5]
输入2：
head = [1,2] , n = 2
输出2：
[2]
思路：
利用双指针，循环中一个指向结尾一个指向离它 n 距离的节点。
循环直到结尾指针到最后一位。
最后删除节点即可
所以代码如下：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//指向 后一个 节点
ListNode f = head;
//指向 前一个 节点
ListNode h = head;
//计算向下走了几位，判断两个指针之间的间距
int ji = 0;
//循环直到 后一个 节点来到最后一位
while(f.next!=null){
//如果两个指针的间距达到了 n 所需要的， h节点 也开始向下走
if(ji==n){
h=h.next;
}else{
//如果没有达到两个指针之间需要的间距，ji++，继续计数
ji++;
}
//每次 f节点 指向下一个节点
f = f.next;
}
//最后删除 h节点 的下一个节点。
h.next = h.next.next;
//返回 head 头结点即可
return head;
}
}
这里因为我们需要删除节点，所以 h 指针需要指向所删除的节点的上一个节点。
用 h.next = h.next.next 即可删除节点。
但是同时，我们会发现一个问题。
如果我们需要删除倒数第 n 个节点，同时链表长度为 n 。
即删除第一个节点，用 上面 的方法则无法正确删除。
因为直到 f 指向最后一个节点，ji 仍然比 n 小 1 。
所以我们需要进行一个判断，判断是否需要删除的是第一个节点。
这里可以根据 ji 是否等于 n 来进行判断。
更改后的代码如下
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode f = head;
ListNode h = head;
int ji = 0;
while(f.next!=null){
if(ji==n){
h=h.next;
}else{
ji++;
}
f = f.next;
}
//如果 ji == n ，说明不是删除第一个，h指针 到了位置。
if(ji==n){
h.next = h.next.next;
}else{//反之直接删除第一个节点，让head = head.next ，返回 head 即可
head = head.next;
}
return head;
}
}
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
例子：
输入1：
1 -> 2 -> 4
1 -> 3 -> 4
l1 = [1,2,4] , l2 = [1,3,4]
输出2：
1 -> 1 -> 2 -> 3 -> 4 -> 4
[1,1,2,3,4,4]
输入2：
l1 = [] , l2 = []
输出2：
[]
这道题不难，一个指针指向 l1 一个指针指向 l2
循环拿个小添加拿个，最后返回即可。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//如果 list1 为空，直接返回 list2
if(list1==null){return list2;}
//如果 list2 为空，直接返回 list1
if(list2==null){return list1;}
//创建一个新节点头结点 temp
ListNode temp = new ListNode();
// z 记住该节点
ListNode z = temp;
//循环
while(true){
//如果 list1 到空，那么下一个节点直接添加 list2 即可
if(list1==null){
temp.next = list2;
break;
//如果 list2 到空，那么下一个节点直接添加 list1 即可
}else if(list2==null){
temp.next = list1;
break;
//如果 list1 的值 比 lisr2 的值 小。新链表下一个节点为 list1节点
}else if(list1.val
