1. 删除链表中等于给定值 val 的所有节点。
假设：我们有这么个链表：
我们需要删除所有date域为key的结点。
假设key为4：
思路（快慢指针）：
1. 我们设置两个指针，一个叫做fast，用于与date域进行判断；另一个叫做slow，用于将所有的链表串联。fast指向head.next；slow指向slow。
如果结果相等：
将fast.next 赋给slow.next ，用于跳过这个指针。
继续向后走：
我们可以知道直到fast为null时，我们就结束了。
3. 考虑特殊情况；1. 我们的fast是指向第二个结点的，可能只有单个结点；2. 我们的思路没有考虑头结点的date域为key的情况。
class Solution {
public ListNode removeElements(ListNode head, int key) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast != null) {
if(fast.date== key) {
slow.next = fast.next;
} else {
slow = fast;
}
fast = fast.next;
}
return head;
}
}我们还缺少一段代码:
if(head.date== key) {
head = head.next;
}对于这段代码放在哪里也需要考虑，如果放在循环之前，那么会有漏掉一个结点的情况，我们来测试一下。
假设key为2：
判断head.date 是否与key相等，结果为真，那么
我们新的head结点的date域还是2，这种情况下是不能解决问题的。
我们可以试着先不管head结点，把其他的结点全部排序好，最后再来处理head结点，所以我们可以把该段代码放在循环之后：
class Solution {
public ListNode removeElements(ListNode head, int key) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast != null) {
if(fast.date== key) {
slow.next = fast.next;
} else {
slow = fast;
}
fast = fast.next;
}
if(head.date== key) {
head = head.next;
}
return head;
}
}我们来看看结果如何：
2. 反转一个单链表。
假设链表为：
我们的最终目的是变成：
我们的思路有很多，但是我们要求只遍历一遍就将链表翻转。
我们有一个最简单的思路，头变尾，尾变头：
将head结点的next变为null；
将第二个结点变为新的head结点原来的head结点接到新的head结点，后面的所有结点也如此。
具体思路：
1. 先创建一个 cur 结点保存 head.next，再将head结点的next域置为null；
2. 创建一个curNext结点，用于保存cur.next ；将head的地址保存到cur.next 中，
3. 将cur赋给head，将curNext赋给cur：
4. 重复2 3 两步操作：
当然我们还需要考虑特殊情况如果head为null，那么直接返回null即可，如果只有head一个结点，那么我们返回head。
代码如下：
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode cur = head.next;
head.next = null;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
}
}结果如下：
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
链接：876. 链表的中间结点 - 力扣（Leetcode）
这题很简单，分析如下：
设置两个指针，一个fast，一个slow，我们要找到中间结点，如果是单数比如5，我们的中间结点元素的下表应该为2，恰好为正中间。如果是双数，比如4，中间结点的下标为：4 / 2 = 2。
那么思路就有了：
快指针fast每次走2步，慢指针slow每次走1步，当fast走到末尾时slow正好走到中间。
代码：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode prve = head;
ListNode cur = head;
while(prve != null && prve.next != null) {
prve = prve.next.next;
cur = cur.next;
}
return cur;
}
}结果：
我们这一题的目的是为了引出下一题：
输入一个链表，输出该链表中倒数第k个结点
4. 输入一个链表，输出该链表中倒数第k个结点
链接：链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
在上一题的基础上，我们去找倒数第k个结点：
思路（快慢指针）：
因为与目标结点相对称的结点，恰好距离fast k - 1 步。
测试：假设上图中目标结点为倒数第二个结点：
fast先走2-1 步
接下来fast和slow一起走：
代码如下：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (k <= 0 || head == null ) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k - 1 != 0) {
fast = fast.next;
if(fast == null) {
return null;
}
k--;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
结果如下：
