精选挑选了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多篇原创文章
