目录
题目一：移除链表元素
（1）题目链接
（2）题目要求
（3）题解
题目二：反转链表
（1）题目链接
（2）题目要求编辑
（3）题解
题目三：链表的中间节点
（1）题目链接
（2）题目要求
题目四：返回倒数第k个节点
（1）题目链接
（2）题目要求
（3）题解
题目五：合并两个有序链表
（1）题目链接
（2）题目要求
（3）题解
题目一：移除链表元素
（1）题目链接
移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/description/
（2）题目要求
（3）题解
操作：
cur代表当前需要删除的节点
prev代表当前需要删除节点cur的前驱节点
如果找到需要删除的节点，prev.next = cur.next;cur = cur.next;
如果没找到所要删除的节点，移动prev节点prev = cur;再移动cur判断下一个节点cur = cur.next;
最后的效果
如何处理头节点就是要删除的节点的情况？
先将头节点以外的删除再来考虑头节点位置即可
if(head.val == val) {
head = head.next;
}
也可先考虑头节点的情况，while循环判断
public void removeAllKey(int val) {
//1. 判空
if (head == null) {
head = head.next;
}
//2. 定义prev 和 cur
ListNode prev = head;
ListNode cur = head.next;
//3.开始判断并且删除
while (cur != null) {
if (cur.val == val) {
//找到了
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
//4.处理头节点
if(head.val == val) {
head = head.next;
}
}public ListNode removeElements(ListNode head, int val) {
// 1. 处理头节点
while (head != null && head.val == val) {
head = head.next;
}
// 2. 如果链表为空，直接返回
if (head == null) {
return head;
}
ListNode cur = head;
// 3. 开始判断并且删除
while (cur.next != null) {
if (cur.next.val == val) {
// 找到了
ListNode del = cur.next;
cur.next = del.next;
} else {
cur = cur.next;
}
}
// 4. 这里不需要再处理头节点，因为在循环开始前已经处理过了
return head;
} 题目二：反转链表
（1）题目链接
反转链表https://leetcode.cn/problems/reverse-linked-list/description/
（2）题目要求
（3）题解
思路：
- 采用头插法，将头节点以外的节点依次插入到头节点前面并改变next的指向
操作：
- 首先我们判断头节点head为空的情况，为空时返回head即可
- cur节点表示什么？定义一个cur节点表示头结点的下一个节点，表示我们从头节点的下一个节点开始进行头插
- curN节点表示什么？curN节点表示记录cur的下一个节点，当我们头插一个节点之后为了不丢失下一个结点的地址，我们需要提前记录下这个节点的地址，以便进行下一次头插
- 在进行一次头插后我们就改变头节点head的位置，同时cur向后移动进行下一次头插
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode cur = head.next;
head.next = null;
while (cur != null) {
ListNode curN = cur.next;
cur.next = head;
head = cur;
cur = curN;
}
return head;
}题目三：链表的中间节点
（1）题目链接
链表的中间节点https://leetcode.cn/problems/middle-of-the-linked-list/description/
（2）题目要求
（3）题解
寻找中间节点用到了非常经典的快慢指针方法
思路：
使用两个指针变量，刚开始都位于链表的第 1 个结点，一个永远一次只走 1 步，一个永远一次只走 2 步，一个在前，一个在后，同时走。这样当快指针走完的时候，慢指针就来到了链表的中间位置。
这道题换一种说法其实就是简单的数学问题，有两个人，fast和slow，fast的速度是2，slow的速度是1，它们从起点同时出发，当fast到达终点时，slow就在路程的中点，而slow所在的位置就是我们要返回的中间节点
操作：
- fast和slow在同一起点，也就是head
- 循环条件是什么？
这里我们要考虑到奇数节点和偶数节点的区别
当链表的节点数为偶数时，fast == null时找到中间节点停止循环
当链表的节点数为奇数时，fast.next == null时找到中间节点停止循环
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
ListNode tmp = fast.next;
fast = tmp.next;
slow = slow.next;
}
return slow;
}题目四：返回倒数第k个节点
（1）题目链接
返回倒数第k个节点https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
（2）题目要求
（3）题解
思路：
因为题目要求是返回导数第k个节点，在这里我们依然使用的是快慢指针方法
我们先让fast走k步，来抵消倒数的这个差值，然后再让fast和slow同时走
操作：
- fast和slow从同一起点head出发
- 先将fast走k步再让它们同时走，直到fast为空时返回slow即可
public int kthToLast(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i = 0;i < k;i++) {
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow.val;
}题目五：合并两个有序链表
（1）题目链接
合并两个有序链表https://leetcode.cn/problems/merge-two-sorted-lists/description/
（2）题目要求
（3）题解
思路：
- 将两个链表的头节点依次进行比较，如果headA.val < headB.val，则tmp.next = headA，让headA往后走一步，tmp也往后走一步；headA.val > headB.val同理
- 如果A链表或B链表中有一个提前遍历完，那么再往后走就指null，这时tmp.next及时接上那个未遍历完的链表节点。
操作：
- 创建一个傀儡节点，用来指向两个链表头节点较小的一个
- 循环条件是什么？在两个链表的长度长度不同时，我们需要当一个链表判断完时接上另一个链表，这时我们要确保短的链表每个节点的val都判断到，也就是两个链表的不能为null，也就是headA != null && headB != null
- 要考虑两个链表空的情况，当A为空时直接指向B即可，否则相反
public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
ListNode newH = new ListNode();
ListNode tmp = newH;
while(headA != null && headB != null) {
if(headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
} else{
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA != null) {
tmp.next = headA;
} else {
tmp.next = headB;
}
return newH.next;
}
