力扣链表OJ面试题，那些你不懂的全新版本解法

????????????????????????????????????????????????孤独的时候看世界更清晰

?前言

数据结构的逻辑性是非常强的，所以单单看代码很难搞懂，这里博主对每一道题目都进行了非常细致的图文详解，每一道题目都是非常经典的面试OJ题，每一道题我都附上了对应的力扣链接，本文主要是较为简单的题目，比较难的题目将会在下一篇博客中为大家讲解，希望对大家有所帮助，谢谢！！

目录

1. 移除链表元素

?1）总代码

2. 反转链表

?2）总代码

3.?链表的中间结点

3）总代码?

4. 链表中倒数第k个结点

4）总代码???

?5.?合并两个有序链表?

?5）总代码

1. 移除链表元素

题目：删除链表中等于给定值 val 的所有节点?

假设我们要删除val=45的节点，那么我们首先要定义一个prev和cur，让prev指向第一个节点，cur指向第二个节点，然后我们判断cur的val是不是45？如果等于那么

prev.next = cur.next; 

这样便完成了该节点的删除，该节点就会被回收?

?接着我们便让cur往后面走一步，但是prev不能动，原因是为了防止下个节点依旧是45，当下个节点不是我们要删除的数时，就让prev向前走，使cur和prev处于同一位置（如下图1），然后再让cur往后走（如下图2）

所以我们这里要分两种情况，一种是下个节点是我们要删除的数，另一种是下个节点不是我们要删除的数

while(   ) { 
    if(cur.val == val) {
    prev.next = cur.next;
        cur = cur.next;
    }else {
        prev = cur;
        cur = cur.next;
}

?当我们走到0x36这个节点，发现是45，满足我们上述代码的if条件?

?走到这里我们自然而然知道了while()的条件，那就是 cur != null ,为什么呢？当走到这一步时候，cur所处的节点56不等于45，所以执行else里面的代码

这样便把所有的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;
}

但是如果我们要在代码开始就先把头节点处理掉，这种情况的话需要加个循环，防止第一第二个节点都是我们要删除的

?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. 反转链表

题目：反转一个单链表?

?这道题要我们做的，其实就是头变尾，尾变头，最终实现下图的效果

总思路：将头节点置为空 ，然后对后续的节点都进行头插，因为头插法本身就可以将链表翻转

具体解决操作：定义cur指向当前需要翻转的节点

?在这里我们可以顺带处理 空表 以及 表里只有一个节点 的情况

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;? //头插

?头插完后，新的头节点就要变成cur所指的节点，即：?head = cur;

然后新的cur应该等于curNext 即：?cur = curNext;

这样便完成了一次反转，我们接着套上循环就可以完成整个链表的反转。上述的代码实现：

while(cur != null) {
    ListNode curNext = cur.next;
    cur.next = head;
    head = cur;
    cur = curNext;
}

?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

然后让 fast? 一次走两步， slow 一次走一步

当 fast 走向空的时候，slow 就是中间位置

原理：有长度为n的线段，A和B在同一个起点，A的速度为B的速度的两倍，当A走到终点时，B刚好走到 n/2 处

?

上面这是个奇数的情况，在偶数条件上一样适用?奇数与偶数情况唯一不一样的地方就是当代码走到最后时：

奇数情况下:? ?fast.next = null;?

偶数情况下：fast = null;

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 步即可

?这种解法可以解决这个问题，但需要求链表的长度，这里博主想跟大家分享另一个方法：

我们首先要关注到一个问题，这个K的取值范围，如果长度为5，这里的 K <= 5? ,? K > 0

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k <= 0 || k > size()) { 
            return null;
        }
    }
}

这里把K值不合法的情况先处理掉了，可能会有人说这样也会求链表的长度啊，先别急，这里只是为了便于理解，暂时这么写，后续会删掉的

?

思路：跟上题一样，先定义一个 fast 和 slow ,假设我们要找倒数第二个节点，也就是说 K=2 ，我们先让fast 走 K - 1 步，如下图：

走完一步后，slow 和 fast 同时走，当 fast 走到 null 时候，slow就是我们要找的节点

这会不会是巧合呢？我们再来看，假设我们要找倒数第三个节点，也就是说 K = 3 ，根据上述思路让 fast 走K-1步，所以fast会先来到如下图所示位置：

然后让 fast 和 slow 同时走，当 fast 走到 null 时，slow就是我们要找的节点，如下图：

这样是不是就能解决问题了，原理是什么呢？

我们回过头来看，我们找倒数第二个节点的时候，是不是从后往前走一步即可，我们找倒数第三个节点的时候，是不是从后往前走两步，依此类推，找倒数第四个节点时候，从后往前走三步，那么当我们要找倒数第K个节点时候，是不是就是从后往前走了 K - 1 步? 而我们的 fast 最后一定会到达null这个最后的位置，相当于一条线段的终点，而我们的 slow 最终会到达我们要找的位置 K ，相当于一条线段的起点，我们回过头看上文给的思路，在一开始的时候，我们的head 和 slow 都在开始位置，如下图一

?我们先让fast先走 K-1 步，为什么？注意这个 K - 1，他是不是 slow 与 fast 之间的距离？也就是slow 和 fast 组成的线段的长度，

然后让slow 和 fast 同时走，是不是就相当于把这条线段往后挪？当fast这个线段的终点到达null的时候，slow这个线段的起点就刚好落在了K位置上，这整个过程类似于我们提前测量好了窗户的大小来制作玻璃（先让fast先走 K-1 步），然后把玻璃挪到窗户那里（让slow 和 fast 同时走），就可以刚刚好安上一样（刚好落在了K位置上），

过程如下图：这里以k = 2 为例子。

1.让fast走 k -1 步

?2.?让slow 和 fast 同时走

?当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。

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所在的那个节点。

??

思路：首先，我们要申请一个虚拟节点(有些书上叫 傀儡节点)，这个节点可能会有一个val值，但是这个值没有意义：

?接着，我们就看两个链表各个节点的val值，哪个值小就往这个虚拟节点后面串：

?

串完之后，headB往后走：

?

再比较 12 和 15 谁小，是不是12小，那么我们就把0x87那个节点的next域改成值为12的节点(0x112)，注意让headA往后面走，然后再比较 15 和 23 谁小，谁小就串到后面，这就是这题的思路

重复上面的过程，当我们发现有一个链表已经走到null，那么我们就不需要再比较了，因为这是个有序链表，我们直接把剩下的另一个链表直接全部串到后面即可，如下两图：

??

??

因为链表本身不带头节点的，我们实际返回的是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. 当有一个链表为空的时候，如下图所示：?

if(headA != null) {  //headB为空时
    tmp.next = headA;
}

if(headB != null) {  //headA为空时
    tmp.next = headB;
}

?4. 最后返回头节点

return newHead.next;

?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;
    }
}

下一篇文章博主将会讲解力扣oj链表较难的题目，感兴趣的小伙伴可以去看看

希望对大家有所帮助，感谢观看！！！?