一起刷好题|《手撕力扣链表题》反转链表、删除链表的倒数第 N 个结点数据结构|链表

?作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
博客首页：是小鱼儿哈
系列专栏：JavaSE学习笔记
每日一句：与其做困难的奴隶，不如做困难的主人。
博主也在学习阶段，如发现问题请告知，非常感谢

目录
一、反转链表
迭代
递归
二、删除链表的倒数第N个结点
小白做法：
设置虚拟头结点的做法
快慢指针法

一、反转链表

文章图片

原题链接：反转链表

迭代其实要反转链表不需要再定义一个新的链表来实现反转，只需要改变原链表next的指向就可以了。从头结点开始，顺次让每个链表结点都指向它的前一个结点就好，头结点的前一个就是空结点，原来最后一个结点不再指向空结点，而改为指向倒数第二个结点。
但要注意的是：改变指向必须从链表的头结点开始，原链表的每一个结点的指向都要改变（要不然会形成死循环的）

// 反转链表，迭代法 class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head; ListNode pre = null; // 定义cur的前一个结点 while (cur != null) { // 因为接下来cur.next的指向会变所有，所以先存一份 ListNode tmp = cur.next; cur.next = pre; // 对该结点的指向进行反转，当前结点指向前一个结点 pre = cur; // 对当前结点的前一个结点进行更新 cur = tmp; // 对当前结点进行更新 } return pre; // 因为当前cur结点已经为空，所以返回他的前一个结点 } }

递归

其实递归对链表的反转思路和上面的迭代法是一样的，只不过是把对链表结点的更新用函数的的递归来完成了

class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head; ListNode pre = null; // 定义cur的前一个结点 return reverse(pre, cur); // 因为当前cur结点已经为空，所以返回他的前一个结点 } public ListNode reverse(ListNode pre, ListNode cur) { // 进行递归操作的那个方法 if(cur == null) return pre; // 递归的出口 ListNode tmp = cur.next; // 保存cur的下一个结点 cur.next = pre; // 反转操作 return reverse(cur, tmp); // 上面这一步做的就是我们前面迭代法中对pre和cur的更新 // pre = cur; cur = tmp = cur.next; } }

二、删除链表的倒数第N个结点

文章图片

原题链接：删除链表的倒数第N个结点

小白做法：

思路：先找到链表的结点数目，以此来得到要删除的结点的坐标，再通过坐标找到要删除链表的前一个结点，以便来进行删除。

注意考虑特殊情况（当要删除的结点是头结点）

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if (head.next == null) { // 当链表中只有一个元素时候，要删除的第n个结点只能是该链表中这个唯一的结点 return null; } ListNode tmp =head; int size = 0; while (tmp != null) { // 遍历得到链表结点数目 tmp = tmp.next; size++; } int index = size - n; // 得到要删除的结点的坐标 if (index == 0) {// 如果要删除的是头结点，无法找到它的前一个结点，所以要进行特判 head = head.next; return head; } ListNode cur = head; for (int i = 0; i < index - 1; ++i) { // 通过遍历让cur结点指向要删除结点的前一个结点 cur = cur.next; } cur.next = cur.next.next; return head; } }

设置虚拟头结点的做法思路和小白做法一样，但因为设置了虚拟头结点，所以不用考虑删除头结点这种特殊情况

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummyHead = new ListNode(0, head); // 定义一个虚拟头结点,并将它指向头结点，这样删除头结点时就不用再专门考虑了 ListNode tmp =head; int size = 0; while (tmp != null) { // 遍历得到链表结点数目 tmp = tmp.next; size++; } int index = size - n; // 得到要删除的结点的坐标 ListNode cur = dummyHead; for (int i = 0; i < index; ++i) { // 通过遍历让cur结点指向要删除结点的前一个结点 cur = cur.next; } cur.next = cur.next.next; return dummyHead.next; // 注意此时虽然head和dummyHead.next都表示对头结点的引用，但他们俩在内存中存放的位置不同， // 当dummyHead.next更改了他的指向时，对head并没有什么影响。所以不能return head; } }

快慢指针法刚才我们看到了，因为题目要求删除的是倒数第n个结点，所以上面的方法都是先要求出链表的长度，再通过长度求出要删除结点的下标，那我们能不能再不求出链表长度的情况下成功删除该结点呢？
我们其实想象一下我们的链表其实是分为两个部分的：倒数第n个结点前面是一部分，倒数第n个结点后面又是一部分。而双指针法正是利用了这个特性来做的。

文章图片

你看，如果我们fast和slow这两个结点引用变量一开始都分别指向我们的虚拟头结点，如果fast先移n个结点，那么是不是此时fast到链表结尾的距离就是我们从虚拟头结点到倒数第n个结点的距离了。
那么我们就可以先让fast先移动n步，然后fast和slow再同时开始移动，直到fast指向了链表的结尾，此时slow不就指向了我们要删除的那个结点了吗？

但要注意的是我们删除结点一般都是要找到该结点的前一个结点，所以我们的fast先要移动n+1步，以便之后让我们的slow指向要删除结点的前一个结点。

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummyHead = new ListNode(0, head); // 定义一个虚拟头结点,并将它指向头结点，这样删除头结点时就不用再专门考虑了 ListNode fast = dummyHead, slow = dummyHead; // 定义两个快慢指针，分别指向该虚拟头节点 for(int i = 0; i < n + 1; ++i) { // fast先移动n+1步 fast = fast.next; } while (fast != null) { slow = slow.next; fast = fast.next; } // 此时slow指向要删除的结点的前一个结点 slow.next = slow.next.next; return dummyHead.next; // 返回头结点 }

小伙伴们，都看到这里了，是不是已经迫不及待的想刷题了，一起冲呀！！！