【精挑细讲】这 10 道链表相关算法题，将助你告别链表问题（上）

精选挑选了9道链表相关是算法题，每道都给出了对应的解答以及技巧，看完这些链表问题，相信你再也不怕链表问题了，建议点赞、收藏。

为了方便大家查找，我这里先给出个目录

1、如何优雅着反转单链表

2、环形单链表约瑟夫问题最优解

3、三种方法带你优雅判断回文链表

4、删除单链表的中间节点

5、将单向链表按某值划分成左边小，中间相等，右边大的形式

6、复制含有随机指针节点的链表

7、将单链表的每K个节点之间逆序

8、将搜索二叉树转换成双向链表

9、删除单链表的第 K个节点

更多算法问题，大家也可以关注我的公众号： 苦逼的码农 ，主要写算法、计算机基础之类的文章，里面已有100多篇原创文章

1、如何优雅着反转单链表

【题目描述】

反转单链表。例如链表为：

1->2->3->4

反转后为

4->3->2->1

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【解答】

方法1

这道题还是挺简单的，当我们在反转一个节点的时候，把一个节点的后驱改为指向它前驱就可以了。这里需要注意的点就是，当你把当前节点的后驱指向前驱的时候，这个时候链表会被截断，也就是说后面的节点和当前节点分开了，所以我们需要一个变量来保存当前节点的后驱，以访丢失。

具体代码如下：

代码如下

//节点
class Node{
    public int value;
    public Node next;
    public Node(int data) {
        this.value = data;
    }
}
复制代码

//反转单链表
    public static Node reverseList(Node head) {
        Node next = null;//指向当前节点的后驱
        Node pre = null;//指向当前节点的前驱
        while (head != null) {
            next = head.next;
            //当前节点的后驱指向前驱
            head.next = pre;
            pre = head;
            //处理下一个节点
            head = next;
        }
        return pre;
复制代码

方法二

这道题也可以用递归来做，假设 方法 reverse() 的功能是将单链表进行逆转。采用递归的方法时，我们可以不断着对子链表进行递归。例如对于如下的链表：

我们对子链表 2->3->4 进行递归，即 Node newList = reverse(head.next)。递归之后的结果如下：

逆转之后子链表 2->3->变为了 4->3->2。 注意，我刚才假设 reverse() 的功能就是对链表进行逆转。不过此时节点 1 仍然是指向节点 2 的。这个时候，我们再把节点1 和 2逆转一下，然后 1 的下一个节点指向 null 就可以了。如图：

递归的结束条件就是：当子链表只有一个节点，或者为 null 时，递归结束。代码如下：

//用递归的方法反转链表
    public static Node reverseList2(Node head){
        if (head == null || head.next == null) {
            return head;
        }
        //递归反转子lian链表
        Node newList = reverseList2(head.next);
        //第三张图
        head.next.next = head;
        head.next = null;
        return newList;
    }
复制代码

问题拓展

题目：反转部分链表节点

【题目描述】

题目：给定一个单向链表的头结点head,以及两个整数from和to ,在单项链表上把第from个节点和第to个节点这一部分进行反转

列如： 1->2->3->4->5->null,from=2,to=4

结果：1->4->3->2->5->null

列如：

1->2->3->null from=1,to=3

结果为3->2->1->null

【要求】

1、如果链表长度为N，时间复杂度要求为O（N),额外空间复杂度要求为O（1）

2、如果不满足1<=from<=to<=N,则不调整

【解答】

这个就直接扔出代码了

public static Node reversePart(Node head, int from, int to) {
        int len = 0;//记录链表的长度
        Node node1 = head;
        Node fPre = null;//指向第 from-1个节点
        Node tPos = null;//指向第 to + 1个节点
        while (node1 != null) {
            len++;
            if(len == from - 1)
                fPre = node1;
            if(len == to + 1)
                tPos = node1;
            node1 = node1.next;
        }
        //判断给定的值是否合理
        if(from > to || from < 1 || to > len)
            return head;
        //把from-to这部分链表进行反转
        //node1指向部分链表的第一个节点
        node1 = fPre == null ? head : fPre.next;
        Node cur = node1.next;//cur指向当前要处理的节点
        node1.next = tPos;//先把第一个节点给反转处理了
        Node next = null;
        while (cur != tPos) {
            next = cur.next;//保存当前节点的下一个节点
            cur.next = node1;
            node1 = cur;
            cur = next;
        }
        if (fPre != null) {
            fPre.next = node1;
            return head;
        }
        return node1;
    }

复制代码

想学习算法大家也可以关注公众号「 苦逼的码农 」，主要写算法、计算机基础之类的文章，里面已有100多篇原创文章哦。

2、环形单链表约瑟夫问题

【题目描述】

【要求】

输入：一个环形单向链表的头节点 head 和报数 m.

返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删除掉。

【解答】

方法1：时间复杂度为 O( n * m)

这道题如果不考虑时间复杂度的话还是挺简单的，就遍历环形链表，每遍历 m 个节点就删除一个节点，知道链表只剩下一个节点就可以了。

代码如下

//时间复杂度为O(n*m)的解决方法
    public static Node josephusKill(Node head, int m) {
        if(head == null || m < 1)
            return head;
        Node last = head;
        //定位到最后一个节点
        while (head.next != last) {
            head = head.next;
        }
        System.out.println(head.value);
        int count = 0;
        while (head.next != head) {
            if (++count == m) {
                head.next = head.next.next;
                count = 0;
            } else {
                head = head.next;
            }
        }
        return head;
    }
复制代码

这个方法的时间复杂度为 O(n * m)。下面用时间复杂度为方法解决。

方法二：时间复杂度为 O(n)

这个方法的难度为：

校：★★★☆

我们可以给环形链表的节点编号，如果链表的节点数为 n, 则从头节点开始，依次给节点编号，即头节点为 1， 下一个节点为2， 最后一个节点为 n.

我们用 f(n) 表示当环形链表的长度为n时，生存下来的人的编号为 f(n)，显然当 n = 1 时，f(n) = 1。假如我们能够找出 f(n) 和 f(n-1) 之间的关系的话，我们我们就可以用递归的方式来解决了。我们假设 人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为

...

m - 2

m - 1

m

m + 1

m + 2

...

进行了一次删除之后，删除了编号为m的节点。删除之后，就只剩下 n - 1 个节点了，删除前和删除之后的编号转换关系为：

删除前 -------- 删除后

... ---------- ...

m - 2 ------- n - 2

m - 1 ------ n - 1

m ---------- 无(因为编号被删除了)

m + 1 ------ 1(因为下次就从这里报数了)

m + 2 ------ 2

... -------- ...

新的环中只有 n - 1 个节点。且编号为 m + 1, m + 2, m + 3 的节点成了新环中编号为 1， 2， 3 的节点。

假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.

这样，我们就得出 f(n) 与 f(n - 1)之间的关系了，而 f(1) = 1.所以我们可以采用递归的方式来做。

代码如下：

//时间复杂度为O(n)
    public static Node josephusKill2(Node head, int m) {
        if(head == null || m < 1)
            return head;
        int n = 1;//统计一共有多少个节点
        Node last = head;
        while (last.next != head) {
            n++;
            last = last.next;
        }
        //直接用递归算出目的编号
        int des = f(n, m);
        //把目的节点取出来
        while (--des != 0) {
            head = head.next;
        }
        head.next = head;
        return head;
    }

    private static int f(int n, int m) {
        if (n == 1) {
            return 1;
        }
        return (getDes(n - 1, m) + m - 1) % n + 1;
    }
复制代码

问题拓展

对于上道题，假设是从第 K 个节点开始报数删除呢？ 又该如何解决呢？

3、三种方法带你优雅判断回文链表

【题目描述】

给定一个链表的头节点 head, 请判断该链表是否为回文结构。

例如：

1->2->1，返回 true.

1->2->2->1, 返回 true。

1->2->3，返回 false。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【解答】

方法1

我们可以利用栈来做辅助，把链表的节点全部入栈，在一个一个出栈与链表进行对比，例如对于链表 1->2->3->2->2，入栈后如图:

然后再逐一出栈与链表元素对比。

这种解法比较简单，时间复杂度为 O(n), 空间复杂度为 O(n)。

代码如下

//方法1
    public static boolean f1(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node temp = head;
        Stack<Node> stack = new Stack<>();
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        while (!stack.isEmpty()) {
            Node t = stack.pop();
            if (t.value != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
复制代码

方法二

真的需要全部入栈吗？其实我们也可以让链表的后半部分入栈就可以了，然后把栈中的元素与链表的前半部分对比，例如 1->2->3->2->2 后半部分入栈后如图：

然后逐个出栈，与链表的前半部分(1->2)对比。这样做的话空间复杂度会减少一半。

代码如下：

//方法2
    public static boolean f(Node head) {
        if(head == null || head.next == null)
            return true;
        Node slow = head;//慢指针
        Node fast = head;//快指针
        Stack<Node> stack = new Stack<>();
        //slow最终指向中间节点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        System.out.println(slow.value);
        slow = slow.next;
        while (slow != null) {
            stack.push(slow);
            slow = slow.next;
        }
        //进行判断
        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            if (head.value != temp.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
复制代码

**方法三：**空间复杂度为 O(1)。

上道题我们有作过链表的反转的，没看过的可以看一下勒： 【链表问题】如何优雅着反转单链表 ]，我们可以把链表的后半部分进行反转，然后再用后半部分与前半部分进行比较就可以了。这种做法额外空间复杂度只需要 O(1), 时间复杂度为 O(n)。

代码如下:

//方法3
    public static boolean f2(Node head) {
        if(head == null || head.next == null)
            return true;
        Node slow = head;//慢指针
        Node fast = head;//快指针
        //slow最终指向中间节点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node revHead = reverse(slow.next);//反转后半部分
        //进行比较
        while (revHead != null) {
            System.out.println(revHead.value);
            if (revHead.value != head.value) {
                return false;
            }
            head = head.next;
            revHead = revHead.next;
        }
        return true;
    }
    //反转链表
    private static Node reverse(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
复制代码

问题拓展

思考：如果给你的是一个环形链表，并且指定了头节点，那么该如何判断是否为回文链表呢？

4、：删除单链表的中间节点

【题目描述】

给定链表的头节点head，实现删除链表的中间节点的函数。

例如：

步删除任何节点；

1->2，删除节点1；

1->2->3，删除节点2；

1->2->3->4，删除节点2；

1->2->3->4-5，删除节点3；

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【解答】

这道题要求删除中间节点，我们可以采用双指针的方法来做，就是用一个快指针和一个慢指针，快指针每次前进两个节点，而慢指针每次前进一个节点。当快指针遍历完节点时，慢指针刚好就在中间节点了。之前写过一篇 一些算法的常用技巧 也有所过指针使用的一些技巧。

不过在做的时候，最好是先把一些特殊情况先处理好，例如删除的可能是第一个节点，也有可能不用删除节点(只有一个节点时就不用删除了。

代码如下

public static Node removeMidNode(Node head) {
        if(head == null || head.next == null)
            return head;
        if (head.next.next == null) {
            return head.next;
        }
        Node fast = head.next.next;//快指针
        Node slow = head;//慢指针

        //slow最终指向中间节点的前驱
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //进行删除
        slow.next = slow.next.next;
        return head;
    }
复制代码

上次拿到删除倒数第 K 个节点的题其实也是可以使用双指针的，但个人认为，那道题使用双指针的方法并没有我上次那个做法优雅，而这次删除中间节点，则用双指针比较优雅。至于原因，可以自己打下代码看看

问题拓展

题目：删除链表中 a / b 处的节点

【题目描述】

给定链表的头节点 head、整数 a 和 b，实现删除位于 a/b 处节点的函数。

例如：

链表：1->2->3->4->5，假设 a/b 的值为 r。

如果 r = 0，不删除任何节点；

如果 r 在区间 (0,1/5] 上，删除节点 1；

如果 r 在区间 (1/5,2/5] 上，删除节点 2；

如果 r 在区间 (2/5,3/5] 上，删除节点 3；

如果 r 在区间 (3/5,4/5] 上，删除节点 4；

如果 r 在区间 (4/5,1] 上，删除节点 5；

如果 r 大于 1，不删除任何节点。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【解答】

可以自己动手做一下或者想一下，我直接扔代码了

//这道题可以转换为删除第 K = (a * n / b)个节点。其中n表示链表节点
    //的个数，但由于(a * n / b)有可能出现小数，所以我们取 K的上限。
    //所谓上限就是大于等于K的最小整数。
    public static Node removeByRatio(Node head, int a, int b) {
        if(a < 1 || a > b)
            return head;
        int n = 0;
        Node cur = head;
        //统计一共有多少个节点
        while (cur != null)
            n++;
        //问题转换为删除第K个节点,取(a * n / b)的整数上限
        int K =  (int)Math.ceil((double)(a * n) / (double)b);
        if(K == 1)
            return head.next;
        if (K > 1) {
            cur = head;
            //定位到第K个节点的前驱
            while (--K != 1) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }

复制代码

最后推广下我的公众号： 苦逼的码农 ，主要写算法、计算机基础之类的文章，里面已有100多篇原创文章

5、将单向链表按某值划分成左边小，中间相等，右边大的形式md

【题目描述】

给定一个单向链表的头结点head,节点的值类型是整型，再给定一个整数privot。实现一个调整链表的函数，将链表调整为左部分都是值小于privot的节点，中间部分都是值等于privot的节点，右部分都是大于privot的节点。且对某部分内部节点的顺序不做要求

例如:链表9-0-4-5-1，pivot=3。

调整后是1-0-4-9-5，

也可以是0-1-9-5-4

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【解答】

这道题在思路上还是比较简单的，但是在实现上还是有一些细节需要主要的。

本题对某部分的内部节点不做要求，一种很简单的方法就是用一个数组来存链表的节点，然后像类似于 快速排序 的分割函数那样，按照某个值把他们进行划分。

不过这样做的话，空间复杂度为 O(N)。我们也可以采取使用3个指针，把原链表依次划分成三个部分的链表，然后再把他们合并起来，这种做法不但空间复杂度为 O(1), 而且内部节点的顺序也是和原链表一样的。虽然思路简单，但在代码实现上也是有很多细节需要注意的，有时间的话希望大家动手打下码。

代码如下

//用三个指针处理，这道题主要是要注意串联链表时的一些细节处理
    public static Node listPartition(Node head, int pivot) {
        Node sB = null;//小的指针头，即small begin
        Node sE = null;//小的指针尾，即 small end
        Node eB = null;//中的指针头，即 equal begin
        Node eE = null;//中的指针尾，即emall end
        Node bB = null;//大的指针头，即 big begin
        Node bE = null;//大的指针尾，即 big end
        Node next = null;//保存下一个节点
        //进行划分
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sB == null) {
                    sB = head;
                    sE = head;
                } else {
                    sE.next = head;
                    sE = sE.next;
                }
            } else if (head.value == pivot) {
                if (eB == null) {
                    eB = head;
                    eE = head;
                } else {
                    eE.next = head;
                    eE = eE.next;
                }
            } else {
                if (bB == null) {
                    bB = head;
                    bE = head;
                } else {
                    bE.next = head;
                    bE = bE.next;
                }
            }
            head = next;
        }
        //把三部分串连起来，串联的时候细节还是挺多的，
        //串联的过程下面代码的精简程度是最学习的部分了
        
        //1.小的与中的串联
        if (sB != null) {
            sE.next = eB;
            eE = eE == null ? sE : eE;
        }
        //2.中的和大的连接
        if (eB != null) {
            eE.next = bB;
        }
        return sB != null ? sB : eB != null ? eB : bB;
    }
复制代码

整理不容易，写这些文章更加不容易，如果你觉得这篇内容对你挺有启发，为了让更多的人看到这篇文章：不妨

1、 点赞 ，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）

2、 关注我和专栏 ，让我们成为长期关系

3、关注公众号「 苦逼的码农 」，主要写算法、计算机基础之类的文章，里面已有100多篇原创文章

大部分的数据结构与算法文章被各种公众号转载相信一定能让你有所收获

我也分享了很多视频、书籍的资源，以及开发工具，欢迎各位的关注，第一时间阅读我的文章。