力扣链表OJ口试题，那些你不懂的全新版本解法
https://i-blog.csdnimg.cn/blog_migrate/894b91cbe11f7d5abb37d113fd0dbed1.png孤独的时间看世界更清楚
前言
数据布局的逻辑性是非常强的，所以单单看代码很难搞懂，这里博主对每一道题目都进行了非常过细的图文详解，每一道题目都是非常经典的口试OJ题，每一道题我都附上了对应的力扣链接，本文主要是较为简单的题目，比力难的题目将会在下一篇博客中为各人解说，希望对各人有所帮助，谢谢！！
目次
1. 移除链表元素
1）总代码
2. 反转链表
2）总代码
3. 链表的中央结点
3）总代码
4. 链表中倒数第k个结点
4）总代码
5. 合并两个有序链表
5）总代码
1. 移除链表元素
题目：删除链表中等于给定值 val 的所有节点
https://i-blog.csdnimg.cn/blog_migrate/dbbdd342e14a2f586e9fa4c7b65bfde1.png
假设我们要删除val=45的节点，那么我们起主要界说一个prev和cur，让prev指向第一个节点，cur指向第二个节点，然后我们判断cur的val是不是45？如果等于那么
prev.next = cur.next;
https://i-blog.csdnimg.cn/blog_migrate/22a2cbd39bc3f79aca75dbf1a5c35f82.png
这样便完成了该节点的删除，该节点就会被回收
https://i-blog.csdnimg.cn/blog_migrate/2768b58db5acc31d7fa9c6276357c7ef.png
接着我们便让cur今背面走一步，但是prev不能动，缘故起因是为了防止下个节点仍旧是45，当下个节点不是我们要删除的数时，就让prev向前走，使cur和prev处于同一位置（如下图1），然后再让cur今后走（如下图2）
https://i-blog.csdnimg.cn/blog_migrate/b4877462c216662fc79c65cff0554b9a.png
https://i-blog.csdnimg.cn/blog_migrate/c99bfe673fbf5c7566451c4fd377ff2a.png
所以我们这里要分两种情况，一种是下个节点是我们要删除的数，另一种是下个节点不是我们要删除的数
while( ) { if(cur.val == val) { prev.next = cur.next;
cur = cur.next; }else { prev = cur; cur = cur.next;} 当我们走到0x36这个节点，发现是45，满足我们上述代码的if条件
https://i-blog.csdnimg.cn/blog_migrate/3b58d3bae3d4d1ae857cb0d8a7c8012e.png
走到这里我们自然而然知道了while()的条件，那就是 cur != null ,为什么呢？当走到这一步时间，cur所处的节点56不等于45，所以实验else里面的代码
https://i-blog.csdnimg.cn/blog_migrate/2f492cca3126de328246667c3f0fc3b1.png
这样便把所有的45删掉了，这个时间我们return head即可，但是我们没有考虑到头节点是不是45的问题，所以我们还要完善，我先把上述过程进行代码实现：
public ListNode removeElements(ListNode head, int val) { ListNode prev = head; //prey表示当前可能要删除的节点的前驱 ListNode cur = head.next; //cur表示当前可能要删除的节点 while(cur != null) { if(cur.val == val) { prev.next = cur.next;
cur = cur.next; }else { prev = cur; cur = cur.next; } } //除了头节点，其他都删除完成了} 到了这一步，除了头节点我们都删除完了，对于头节点的处理，着实很简单：
if(head.val == val) {
head = head.next;
} 但是如果我们要在代码开始就先把头节点处理掉，这种情况的话必要加个循环，防止第一第二个节点都是我们要删除的
https://i-blog.csdnimg.cn/blog_migrate/2e1975ca1810874e2690b46dbe75a77e.png
1）总代码
class Solution { public ListNode removeElements(ListNode head, int val) { if(head == null) { return null; } ListNode prev = head; //prey表示当前可能要删除的节点的前驱 ListNode cur = head.next; //cur表示当前可能要删除的节点 while(cur != null) { if(cur.val == val) { prev.next = cur.next;
cur = cur.next; }else { prev = cur; cur = cur.next; } //除了头节点，其他都删除了 if(head.val == val) { head = head.next; } } return head; }}2. 反转链表
题目：反转一个单链表
这道题要我们做的，着实就是头变尾，尾变头，终极实现下图的效果
https://i-blog.csdnimg.cn/blog_migrate/3cacf8e046e53f33f5b351db1dde37a9.png
总思路：将头节点置为空 ，然后对后续的节点都进行头插，由于头插法本身就可以将链表翻转
具体解决操作：界说cur指向当前必要翻转的节点
https://i-blog.csdnimg.cn/blog_migrate/4fad0d32b35e75e9bce4ba0f3931ba49.png
在这里我们可以顺带处理 空表 以及 表里只有一个节点 的情况
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) {return head;}
if(head.next == null) {return head;}
ListNode cur = head.next;
head.next = null;
}
} 这时间 头节点 为空，我们对 cur 进行头插法，注意：在头插前要先记载一下 cur.next 不然后续的节点会丢失，即：
ListNode curNext = cur.next; //记载cur.next
cur.next = head; //头插
https://i-blog.csdnimg.cn/blog_migrate/8f523a716c4a94e2b3c7c144f03a0e09.png
头插完后，新的头节点就要酿成cur所指的节点，即： head = cur;
https://i-blog.csdnimg.cn/blog_migrate/6b4c4d506a0ac6780632fcd7719376c3.png
然后新的cur应该等于curNext 即： cur = curNext;
https://i-blog.csdnimg.cn/blog_migrate/acefc62e853d7a42d478f01a0844fedb.png
这样便完成了一次反转，我们接着套上循环就可以完成整个链表的反转。上述的代码实现：
while(cur != null) {
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}https://i-blog.csdnimg.cn/blog_migrate/c0f3c6d700b5bfe49fa395428e7338f8.png
2）总代码
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) {return head;}
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 的非空单链表，返回链表的中央结点。如果有两个中央结点，则返回第二个中央结点。
第一种方法：链表长度÷2 即可拿到中央节点，但是这种解法不是非常好
接下来博主解说第二种方法：
先界说一个 fast 和 slow
https://i-blog.csdnimg.cn/blog_migrate/2a02261af32d2f4932106d8856a05033.png
然后让 fast 一次走两步， slow 一次走一步
https://i-blog.csdnimg.cn/blog_migrate/5151c9560ff05b6c1b4474a10b91004b.png
当 fast 走向空的时间，slow 就是中央位置
https://i-blog.csdnimg.cn/blog_migrate/6bf56917acafdd3f0c78da622c49d00c.png
原理：有长度为n的线段，A和B在同一个起点，A的速度为B的速度的两倍，当A走到尽头时，B刚好走到 n/2 处
https://i-blog.csdnimg.cn/blog_migrate/7b9f41b20e199e5e18e4dca62ec70c1b.png
https://i-blog.csdnimg.cn/blog_migrate/c84ed014b7ba6a1fe55caa9a7f11625e.png
上面这是个奇数的情况，在偶数条件上一样实用
https://i-blog.csdnimg.cn/blog_migrate/c7ad7468b37068291527e820e8424bb5.png
奇数与偶数情况唯一不一样的地方就是当代码走到末了时：
奇数情况下: fast.next = null;
偶数情况下：fast = null;
https://i-blog.csdnimg.cn/blog_migrate/1fd243f83917d93fd50b5b8d99a9e4c1.png
3）总代码
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}4. 链表中倒数第k个结点
题目：输入一个链表，输出该链表中倒数第k个结点。
思路：界说一个 cur 在头节点位置，如果我们要找倒数第3个节点，那么就让cur走 length - 3 步即可到达目标位置，如果我们要找倒数第2个节点，那么就让cur走 length - 2 步即可
https://i-blog.csdnimg.cn/blog_migrate/29597915eb9b3e7029a39e3acf301f22.png
这种解法可以解决这个问题，但必要求链表的长度，这里博主想跟各人分享另一个方法：
我们起主要关注到一个问题，这个K的取值范围，如果长度为5，这里的 K <= 5 , K > 0
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0 || k > size()) {
return null;
}
}
} 这里把K值不合法的情况先处理掉了，可能会有人说这样也会求链表的长度啊，先别急，这里只是为了便于明白，暂时这么写，后续会删掉的
https://i-blog.csdnimg.cn/blog_migrate/32eb8fa9c93d80cc6ac66664a26b36f2.png
思路：跟上题一样，先界说一个 fast 和 slow ,假设我们要找倒数第二个节点，也就是说 K=2 ，我们先让fast 走 K - 1 步，如下图：
https://i-blog.csdnimg.cn/blog_migrate/51e669ea95e83efc87a376fc168b4c9c.png
走完一步后，slow 和 fast 同时走，当 fast 走到 null 时间，slow就是我们要找的节点
https://i-blog.csdnimg.cn/blog_migrate/9351b61d8683a2d58366fdebb8f6b58b.png
这会不会是巧合呢？我们再来看，假设我们要找倒数第三个节点，也就是说 K = 3 ，根据上述思路让 fast 走K-1步，所以fast会先来到如下图所示位置：
https://i-blog.csdnimg.cn/blog_migrate/f42534dfcae568c643a5195eca30b2bf.png
然后让 fast 和 slow 同时走，当 fast 走到 null 时，slow就是我们要找的节点，如下图：
https://i-blog.csdnimg.cn/blog_migrate/4e30583fc698569d4c9372b79b5bca94.png
这样是不是就能解决问题了，原理是什么呢？
我们回过头来看，我们找倒数第二个节点的时间，是不是从后往前走一步即可，我们找倒数第三个节点的时间，是不是从后往前走两步，依此类推，找倒数第四个节点时间，从后往前走三步，那么当我们要找倒数第K个节点时间，是不是就是从后往前走了 K - 1 步? 而我们的 fast 末了肯定会到达null这个末了的位置，相称于一条线段的尽头，而我们的 slow 终极会到达我们要找的位置 K ，相称于一条线段的起点，我们回过头看上文给的思路，在一开始的时间，我们的head 和 slow 都在开始位置，如下图一
https://i-blog.csdnimg.cn/blog_migrate/3497593e5058269c35087300d7e1087a.png
我们先让fast先走 K-1 步，为什么？注意这个 K - 1，他是不是 slow 与 fast 之间的距离？也就是slow 和 fast 构成的线段的长度，
https://i-blog.csdnimg.cn/blog_migrate/4745bd25b4a86a76d7fa7de86cb76782.png
然后让slow 和 fast 同时走，是不是就相称于把这条线段今后挪？当fast这个线段的尽头到达null的时间，slow这个线段的起点就刚好落在了K位置上，这整个过程类似于我们提前丈量好了窗户的巨细来制作玻璃（先让fast先走 K-1 步），然后把玻璃挪到窗户那里（让slow 和 fast 同时走），就可以刚刚好安上一样（刚好落在了K位置上），
过程如下图：这里以k = 2 为例子。
1.让fast走 k -1 步
https://i-blog.csdnimg.cn/blog_migrate/dd5a916bf64fd3d13984e3e81386f54e.png
2. 让slow 和 fast 同时走
https://i-blog.csdnimg.cn/blog_migrate/d6cf8507bfdfd41f519d7983b5578a3e.png
当fast走到null的时间就制止，这个时间slow所处位置就是我们要找的K.
代码实现如下：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0 || k > size()) {
return null;
}
if(head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
int count = 0;
while(count != k-1) {
fast = fast.next;
count++;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
} 我们前面说了k > size() 这个条件只是为了便于明白先这样写的，后续是会删掉的，我们如今处理这个条件，我们设置这个条件的目标是为了什么？着实就是怕K的值太大，超过我们的表长，但是我们这个方法是不是在一开始就预先算好了k值？（fast 先走 k-1 步）如果k值太大，fast还没有走到 k-1 步的时间就已经超过表长了，也就是说 fast.next == null; 所以我们可以在（fast 先走 k-1 步）这段代码处添加一个if()else()语句，如果 fast.next ！= null; 那就让fast继续走 k-1 步，否则返回null。
https://i-blog.csdnimg.cn/blog_migrate/4000bfcd4d5123676b063af79a52bca1.png
4）总代码
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0) {
return null;
}
if(head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
int count = 0;
while(count != k-1) {
if(fast.next != null) {
fast = fast.next;
count++;
}else {
return null;
}
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
} 5. 合并两个有序链表
题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点构成的
我们以下图两个链表为例。将两个链表合成一个，那么我们在布局上就要改变他，要注意这是有序链表，所以是升序的。那么头节点就应该酿成headB所在的谁人节点。
https://i-blog.csdnimg.cn/blog_migrate/ec6cd26f450929d1bc1e715ee1b28ad2.png
思路：起首，我们要申请一个假造节点(有些书上叫 傀儡节点)，这个节点可能会有一个val值，但是这个值没有意义：
https://i-blog.csdnimg.cn/blog_migrate/1c1bd385e81ea45291ae9fab06a03bd8.png
接着，我们就看两个链表各个节点的val值，哪个值小就往这个假造节点背面串：
https://i-blog.csdnimg.cn/blog_migrate/1da66e7d3b76e6a37f040abee6fc674a.png
串完之后，headB今后走：
https://i-blog.csdnimg.cn/blog_migrate/5355ff10e6fc525ff3d1bef07a6807ad.png
再比力 12 和 15 谁小，是不是12小，那么我们就把0x87谁人节点的next域改成值为12的节点(0x112)，注意让headA今背面走，然后再比力 15 和 23 谁小，谁小就串到背面，这就是这题的思路
重复上面的过程，当我们发现有一个链表已经走到null，那么我们就不必要再比力了，由于这是个有序链表，我们直接把剩下的另一个链表直接全部串到背面即可，如下两图：
https://i-blog.csdnimg.cn/blog_migrate/615f491339742c095e476454fb40f662.png
https://i-blog.csdnimg.cn/blog_migrate/30e178677c5d3af9117b68f04b928b98.png
由于链表本身不带头节点的，我们实际返回的是0x87，也就是值为6的这个节点，那么如何返回呢？着实很简单：
return newHead.next; 假造节点在这里起到标记作用
思路总结：
1.创建假造节点
ListNode newHead = new ListNode(-1); 2.比力两个链表的数
这有个地方要注意！！我们能直接动假造节点的next域去指向值较小的谁人节点吗？我们整个过程是不断的去串较小值的节点，这个过程会反复用到 newHead.next = xx； 如果直接改变假造头节点的next域，那么我们末了返回的时间会无法找到头节点，所以我们界说一个临时变量tmp，让tmp去走
ListNode tmp = newHead;
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;
}
} 3. 当有一个链表为空的时间，如下图所示：
https://i-blog.csdnimg.cn/blog_migrate/cddbc057261da45a9ec7c8aa97075370.png
if(headA != null) {//headB为空时
tmp.next = headA;
}
if(headB != null) {//headA为空时
tmp.next = headB;
} 4. 末了返回头节点
return newHead.next; https://i-blog.csdnimg.cn/blog_migrate/8dd2142c1dabc5c026824ea671df47ca.png
5）总代码
public class Solution {
public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
ListNode newHead = new ListNode(-1);//创建虚拟节点
ListNode tmp = newHead;
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;
}
if(headB != null) {
tmp.next = headB;
}
return newHead.next;
}
} https://i-blog.csdnimg.cn/blog_migrate/225a59ddfaf416adbe27b57b9b30bb4e.png
下一篇文章博主将会解说力扣oj链表较难的题目，感兴趣的小伙伴可以去看看
希望对各人有所帮助，感谢观看！！！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]