前言
最近打卡力扣的时候又打卡到了几道相似的题目，同时这个正好也是我的薄弱的地方，所以在这里记录一下，来让我对链表的理解更加深刻，话不多说，直接看下面的题目
题目描述
1. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。?
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
那么在力扣里面是给出了ListNode的描述的，如下代码所示：
/**
* 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; }
* }
*/?因此我们就可以开始想我们的解题思路了
①如果两个链表中有一个为空的话，那么结果必然是另外一个链表
②我们需要一次比较链表的每个节点，然后找到合适的位置进行插入，也就是说，我们首先比较两个链表的首元素，如果第一个链表的更小，那么我们就用第一个链表作为当前主链表，找寻主链表的next，此时就要将链表一的第二个元素和链表二的第二个元素进行比较，如果链表二的元素还是大于链表一，那么下一步还是在链表一中进行操作；否则会转换到链表二中间。
如下图过程：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null&&list2==null){
return null;
}
else if(list1==null&&list2!=null)
{
return list2;
}
else if(list1!=null&&list2==null)
{
return list1;
}
else if(list1.val<list2.val){
list1.next=mergeTwoLists(list1.next,list2);
return list1;
}
else
{
list2.next=mergeTwoLists(list1,list2.next);
return list2;
}
}
}?2. 删除有序链表倒数第N个节点
?给你一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
对于这个题目，首先，我们需要知道ListNode是怎么用的，其实它在java底层中并不存在，只是我们认为定义的一个类的实现而已，所以在这里力扣是给出了相关的类的描述的，如下所示：
/**
* 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; }
* }
*/好了，有了上面的描述我们就可以知道对应的ListNode的描述以及一些简单的操作了
方法一：计算链表的长度
因为这里是要删除倒数为n的节点，那么实际做的时候我们要做的就是删除正向数的对应节点，那么这里的难点就在于怎么求这个节点？
这个时候，我们添加一个新的节点指向我们需要操作的节点，然后这个时候后面的节点就是从1开始的了，然后计算我们需要删除的那个节点的位置就是length-n+1
最后我们可以得到下面的代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode start = new ListNode(0,head); //新建一个头结点之前的结点指向头节点
ListNode nextnode = new ListNode();
int length = getLength(head); //获取链表长度
nextnode = start;
for(int i = 1;i< length-n+1;i++){
nextnode = nextnode.next; //移动指针
}
nextnode.next = nextnode.next.next; //删除指定结点
ListNode res = start.next;
return res;
}
public int getLength(ListNode head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
}方法二：栈的方法
这里是反向操作，那么我们是不是可以想一下我们曾经学过的一些存放数据的方式，我们就可以想到---栈；栈属于先进后出，正好出栈的时候的第n个就是我们想要的那个数据了
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
Deque<ListNode> stack = new LinkedList<ListNode>();
ListNode cur = dummy;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
for (int i = 0; i < n; ++i) {
stack.pop();
}
ListNode prev = stack.peek();
prev.next = prev.next.next;
ListNode ans = dummy.next;
return ans;
}
}
方法三：双指针
我们也可以在不预处理出链表的长度，以及使用常数空间的前提下解决本题。
由于我们需要找到倒数第 nn 个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 nn 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 nn 个节点。
具体地，初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 nn。此时first 和 second 之间间隔了 n?1 个节点，即 first 比 second 超前了 nn 个节点。
在这之后，我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first 为空指针）时second 恰好指向倒数第 n 个节点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; ++i) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
ListNode ans = dummy.next;
return ans;
}
}
总结
有了上面的题目的讲解，对链表也有了一些了解，其实ListNode的实现和LinkedList是很像的，只是说ListNode在java底层中并没有描述，所以需要我们自定义这个类；但是LinkedList是实现了的。
对于ListNode的删除操作，我们应该会使用我们之前学到的栈的知识，就如这里第二题，我们是反向给位置的情况下，我们就可以使用我们之前学的栈的知识来求解。
同时在这里我会出现的一个错误就是：链表是不存在求Length的，他在空间上是不连续的，所以不能这么操作！【对我自己说的！一定要记住！】