【链表反转】介绍几种常见的链表反转方法(递归、迭代、穿针引线法)。
目录
一、链表操作定义
1.1、链表结构定义
1.2、链表工具类
二、反转整个链表
2.1、常规方法
(1)【头插法】具体代码实现
(2)【头插法】画图解析
(3)【头插法】优化
2.2、递归方法
(1)【递归】代码实现
(2)【递归】画图解析
2.3、迭代方法
(1)【迭代】代码实现
(2)【迭代】画图解析
三、反转部分链表
3.1、拼接三段链表
3.2、【头插法】穿针引线法
一、链表操作定义
1.1、链表结构定义
public class ListNode {
public int val;
public ListNode next;
public ListNode() {};
public ListNode(int val) {
this.val = val;
};
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
};
}
1.2、链表工具类
public class ListNodeUtil {
public static ListNode getHead(int[] nums) {
// 定义哑节点
ListNode dummy = new ListNode(-1);
ListNode head = dummy;
for (int i = 0; i < nums.length; i++) {
head.next = new ListNode(nums[i]);
head = head.next;
}
// 返回头结点
return dummy.next;
}
public static void printListNode(ListNode head) {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val);
if (temp.next != null) {
System.out.print("-->");
}
temp = temp.next;
}
System.out.println();
}
}
二、反转整个链表
2.1、常规方法
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。
public class ListNodeUtil {
public static ListNode getHead(int[] nums) {
// 定义哑节点
ListNode dummy = new ListNode(-1);
ListNode head = dummy;
for (int i = 0; i < nums.length; i++) {
head.next = new ListNode(nums[i]);
head = head.next;
}
// 返回头结点
return dummy.next;
}
public static void printListNode(ListNode head) {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val);
if (temp.next != null) {
System.out.print("-->");
}
temp = temp.next;
}
System.out.println();
}
}
二、反转整个链表
2.1、常规方法
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。
第一种想到的链表反转方法,就是遍历链表,然后采用【头插法】来创建一个新的链,这样子就把原先链表进行了反转。
(1)【头插法】具体代码实现
public class HeadInsertion {
public static ListNode reverseListNode(ListNode head) {
// 创建一个新链表
ListNode dummy = new ListNode(-1);
ListNode temp = head;
while (temp != null) {
// 【头插法】: 每次将新的结点直接插入头结点后面
ListNode node = new ListNode(temp.val);
node.next = dummy.next;
dummy.next = node;
// 遍历下一个链表结点
temp = temp.next;
}
// 返回反转后的结点
return dummy.next;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5};
System.out.println("--------- 原先链表 ----------");
ListNode head = ListNodeUtil.getHead(nums);
ListNodeUtil.printListNode(head);
System.out.println("--------- 反转链表 ----------");
ListNode reverseHead = reverseListNode(head);
ListNodeUtil.printListNode(reverseHead);
}
}
反转后的结果如下所示:
(2)【头插法】画图解析
【头插法】操作链表的核心代码:
// 【头插法】: 每次将新的结点直接插入头结点后面 // node: 表示当前待插入的结点 ListNode node = new ListNode(temp.val); // 首先将 node 下一个结点指向 head 头结点下一个结点 node.next = head.next; // 将 head 头结点下一个结点指向 node 结点 head.next = node;
【头插法】大致原理图如下所示:
(3)【头插法】优化
前面的【头插法】每次都会创建一个新的【ListNode】结点,这显然有点浪费内存空间了,我们其实可以直接利用原先链表的结点,从而避免创建新结点。
public static ListNode reverseListNode(ListNode head) {
// 创建一个新链表
ListNode dummy = new ListNode(-1);
ListNode temp = head;
while (temp != null) {
// 保存当前 temp 结点
ListNode node = temp;
// temp 结点移动到下一个链表结点
temp = temp.next;
// 【头插法】: 每次将新的结点直接插入头结点后面
node.next = dummy.next;
dummy.next = node;
}
// 返回反转后的结点
return dummy.next;
}
前面的【头插法】每次都会创建一个新的【ListNode】结点,这显然有点浪费内存空间了,我们其实可以直接利用原先链表的结点,从而避免创建新结点。
这种利用原先结点的方式,需要定义一个变量保存原先链表结点,然后将temp结点移动到下一个结点,之后才可以进行【头插法】操作。
2.2、递归方法
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。
(1)【递归】代码实现
public class RecursionReverse {
public static ListNode reverseListNode(ListNode head) {
// 递归终止条件: 当前结点、下一个结点为 null 时候, 递归结束
if (head == null || head.next == null) {
return head;
}
// 递归逻辑: 继续下一个结点的递归
ListNode newHead = reverseListNode(head.next);
// 递归结束后: 逆转两个结点的顺序
head.next.next = head;
head.next = null;
return newHead;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5};
System.out.println("--------- 原先链表 ----------");
ListNode head = ListNodeUtil.getHead(nums);
ListNodeUtil.printListNode(head);
System.out.println("--------- 反转链表 ----------");
ListNode reverseHead = reverseListNode(head);
ListNodeUtil.printListNode(reverseHead);
}
}
(2)【递归】画图解析
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。
public class RecursionReverse {
public static ListNode reverseListNode(ListNode head) {
// 递归终止条件: 当前结点、下一个结点为 null 时候, 递归结束
if (head == null || head.next == null) {
return head;
}
// 递归逻辑: 继续下一个结点的递归
ListNode newHead = reverseListNode(head.next);
// 递归结束后: 逆转两个结点的顺序
head.next.next = head;
head.next = null;
return newHead;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5};
System.out.println("--------- 原先链表 ----------");
ListNode head = ListNodeUtil.getHead(nums);
ListNodeUtil.printListNode(head);
System.out.println("--------- 反转链表 ----------");
ListNode reverseHead = reverseListNode(head);
ListNodeUtil.printListNode(reverseHead);
}
}
(2)【递归】画图解析
递归的方式,比较难以理解,并且递归需要额外的空间复杂度【O(n)】,这和递归的次数有关。
2.3、迭代方法
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。
(1)【迭代】代码实现
public class IterationReverse {
public static ListNode reverseListNode(ListNode head) {
// 当前结点
ListNode curr = head;
// 保存当前节点的前一个结点
ListNode newHead = null;
// 【迭代】开始遍历链表
while (curr != null) {
// 保存下一个结点
ListNode next = curr.next;
// 当前结点的下一个结点指向前一个结点位置
curr.next = newHead;
// 前一个结点指向当前结点
newHead = curr;
// 当前结点移动到下一个结点
curr = next;
}
// 返回头结点
return newHead;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5};
System.out.println("--------- 原先链表 ----------");
ListNode head = ListNodeUtil.getHead(nums);
ListNodeUtil.printListNode(head);
System.out.println("--------- 反转链表 ----------");
ListNode reverseHead = reverseListNode(head);
ListNodeUtil.printListNode(reverseHead);
}
}
(2)【迭代】画图解析
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。
public class IterationReverse {
public static ListNode reverseListNode(ListNode head) {
// 当前结点
ListNode curr = head;
// 保存当前节点的前一个结点
ListNode newHead = null;
// 【迭代】开始遍历链表
while (curr != null) {
// 保存下一个结点
ListNode next = curr.next;
// 当前结点的下一个结点指向前一个结点位置
curr.next = newHead;
// 前一个结点指向当前结点
newHead = curr;
// 当前结点移动到下一个结点
curr = next;
}
// 返回头结点
return newHead;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5};
System.out.println("--------- 原先链表 ----------");
ListNode head = ListNodeUtil.getHead(nums);
ListNodeUtil.printListNode(head);
System.out.println("--------- 反转链表 ----------");
ListNode reverseHead = reverseListNode(head);
ListNodeUtil.printListNode(reverseHead);
}
}
(2)【迭代】画图解析
依次类推,迭代完成之后,整个链表就被反转了。
三、反转部分链表
3.1、拼接三段链表
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求反转链表中的部分结点。
- 例如:反转链表中第2个到第4个结点,使其成为【1-->4-->3-->2-->5】的结果。
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求反转链表中的部分结点。
- 例如:反转链表中第2个到第4个结点,使其成为【1-->4-->3-->2-->5】的结果。
解决思路:
- 找到第一段链表。
- 找到需要反转的那一段链表,然后将其单独反转。
- 找到最后一段的链表。
- 三段链表找到之后,将其拼接成一个完整的链表。
public class ReverseNode {
public static ListNode reverseListNode(ListNode head, int left, int right) {
// 1、找到第一段链表
ListNode ans = new ListNode(-1, head);
ListNode pre = ans;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
// 2、找到第二段链表
ListNode midHead = pre.next;
ListNode mid = midHead;
pre.next = null; // 断开第一段链表
for (int i = 0; i < right - left; i++) {
mid = mid.next;
}
// 3、找到第三段链表
ListNode lastHead = mid.next;
mid.next = null; // 断开第二段链表
// 4、反转中间链表
ListNode newHead = reverse(midHead);
ListNode temp = newHead;
while (temp != null && temp.next != null) {
temp = temp.next;
}
// 5、拼接链表
pre.next = newHead;
temp.next = lastHead;
return ans.next;
}
public static ListNode reverse(ListNode head) {
ListNode newHead = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = newHead;
newHead = curr;
curr = next;
}
return newHead;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5};
System.out.println("--------- 原先链表 ----------");
ListNode head = ListNodeUtil.getHead(nums);
ListNodeUtil.printListNode(head);
System.out.println("--------- 反转链表 ----------");
ListNode reverseHead = reverseListNode(head, 2, 4);
ListNodeUtil.printListNode(reverseHead);
}
}
3.2、【头插法】穿针引线法
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求反转链表中的部分结点。
- 例如:反转链表中第2个到第4个结点,使其成为【1-->4-->3-->2-->5】的结果。
public class ReverseNode2 {
public static ListNode reverseListNode(ListNode head, int left, int right) {
// 1、找到第一段链表
ListNode ans = new ListNode(-1, head);
ListNode pre = ans;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
// 2、开始反转链表
ListNode curr = pre.next;
ListNode next = null;
for (int i = 0; i < right - left; i++) {
// 首先保存当前结点的下一个结点
next = curr.next;
// 将当前结点指向next结点的下一个结点
curr.next = next.next;
// 将next结点指向当前curr结点
next.next = pre.next;
// 将pre前一个结点指向next结点
pre.next = next;
}
return ans.next;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5};
System.out.println("--------- 原先链表 ----------");
ListNode head = ListNodeUtil.getHead(nums);
ListNodeUtil.printListNode(head);
System.out.println("--------- 反转链表 ----------");
ListNode reverseHead = reverseListNode(head, 2, 4);
ListNodeUtil.printListNode(reverseHead);
}
}
问题描述:
- 有一个链表,【1-->2-->3-->4-->5】,要求反转链表中的部分结点。
- 例如:反转链表中第2个到第4个结点,使其成为【1-->4-->3-->2-->5】的结果。
运行结果如下所示:
链表的操作,关键在于需要理清楚每个结点之间如何指向,确实有一点难以理解,可以借助图形理解。
小试牛刀:
- 206. 反转链表
- 92. 反转链表 II



