
mzoe666888
V1
2022/04/16阅读:18主题:兰青
内卷大厂系列《链表反转三连击》
大厂高频算法面试题:《链表反转系列》,面试官想考察的目的:手稳不稳,coding能力,指针指向问题,链表反转几乎是高频中高频,您将学到通过有限变量即可实现链表反转,快来一起学习吧!
一、反转单向链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:

输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
1、分析
给定一个单链表的头head,完成链表的逆序调整。
方法一:有限变量搞定,定义两个变量,pre指针,next指针,pre指针指向当前节点的上一个节点,next指针指向当前节点的下一个节点。最优解,时间复杂度O(N),额外空间复杂度O(1)
方法二:递归
2、实现
1、方法一
public static class ListNode {
int val;
ListNode next;
}
public static ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
2、方法二
public static class ListNode {
int val;
ListNode next;
}
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newList = reverseList(head.next);
head.next.next = head;
head.next = null;
return newList;
}
二、反转双向链表
给定一个双链表的头head,完成链表的逆序调整
1、分析
提前记录下一个节点next,当前节点的next指向pre,当前节点的last指向next,pre的next指向当前节点,当前节点跳下一个
2、实现
// 双链表定义
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
// 双链表反转(两个指针搞定)
public static DoubleNode reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
三、反转部分单向链表
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
示例 1:

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]
示例 2:
输入:head = [5], left = 1, right = 1
输出:[5]
进阶: 你可以使用一趟扫描完成反转吗?
1、分析
可能存在换头的情况,所以函数应该返回调整后的新节点。
方法一:遍历一遍链表,先找到left和right节点,即反转链表的开始部分和结束部分。
-
先判断是否满足 1≤left≤right≤N,如果不满足,则直接返回原来的头节点。 -
找到第left-1个节点fPre和第right+1个节点tPos,fPre就是要反转部分的前一个节点,tPos是反转部分的后一个节点。把反转部分先反转,然后正确的连接fPre和tPos -
如果fPre为null,说明反转部分是包含头节点的,则返回新的头节点,如果fPre不为null,则返回旧的头节点。
方法二:利用头插法进行反转链表,待反转的节点每次都往头部插入。
2、实现
1、方法一
public static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
// 找到反转链表的开始节点和结束节点,正常反转
public ListNode reverseBetween(ListNode head, int from, int to) {
int len = 0;
ListNode node1 = head;
ListNode fPre = null; // from节点的前一个节点
ListNode tPos = null; // to节点的下一个节点
while (node1 != null) { // 找到反转链表开始节点的前一个节点和结束节点的下一个节点
len++;
fPre = len == from - 1 ? node1 : fPre;
tPos = len == to + 1 ? node1 : tPos;
node1 = node1.next;
}
if (from > to || from < 1 || to > len) {
return head;
}
node1 = fPre == null ? head : fPre.next;
ListNode node2 = node1.next;
node1.next = tPos;
ListNode next = null;
while (node2 != tPos) { // 反转from到to上的节点
next = node2.next;
node2.next = node1;
node1 = node2;
node2 = next;
}
if (fPre != null) {
fPre.next = node1;
return head;
}
return node1;
}
2、方法二
public static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public static ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || left == right) {
return head;
}
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode pre = newHead;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode next = null;
for (int i = 0; i < right - left; i++) {
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return newHead.next;
}
四、总结
链表相关的问题几乎都是coding问题,手稳不稳!指针指向问题!
单链表:值,一条next指针
双链表:值,一条pre指针,一条next指针
玩出无尽的花样!
作者介绍

mzoe666888
V1