链表全部翻转、翻转前n个元素（双指针法，O(n)时间复杂度 O(1)空间复杂度）

66 阅读 0 评论 44 点赞

我是靠谱客的博主任性大米，最近开发中收集的这篇文章主要介绍链表全部翻转、翻转前n个元素（双指针法，O(n)时间复杂度 O(1)空间复杂度），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给你一个单链表，请将其翻转。
我们使用双指针法进行翻转，仅需要遍历一次。

链表节点类，自写的

package link;
/**
* link list node class
* @author humorchen
* @date 2023/1/31 14:43
*/
public class Node {
public int val;
public Node next;
}

链表辅助类，自己写的

package link;
/**
* util for link list
* @author humorchen
* @date 2023/1/31 14:44
*/
public class LinkListUtil {
/**
* 生成链表
* @param len
* @return
*/
static Node newList(int len) {
Node head = null, p = null;
while (len > 0) {
Node node = new Node();
node.val = len;
if (p == null) {
head = node;
} else {
p.next = node;
}
p = node;
--len;
}
return head;
}
/**
* 打印链表
* @param head
*/
static void print(Node head) {
Node p = head;
System.out.print("link list：");
while (p != null) {
System.out.print(p.val + " ");
p = p.next;
}
System.out.println();
}
}

翻转整个链表

link list：10 9 8 7 6 5 4 3 2 1
link list：1 2 3 4 5 6 7 8 9 10

/**
* reverse a node list
* @author humorchen
* @date 2023/1/31 14:21
*/
public class ReverseLinkList {
public static void main(String[] args) {
// 产生一个链表
Node list = LinkListUtil.newList(10);
// 打印该链表
LinkListUtil.print(list);
// 翻转链表
Node reversedList = reverse(list);
// 打印翻转后的链表
LinkListUtil.print(reversedList);
}
/**
* 将链表翻转
* @param head
* @return
*/
static Node reverse(Node head) {
// pre为前一个节点（想象的），cur为当前节点，从头结点开始遍历
Node pre = null, cur = head;
// 当前节点不为空，则继续遍历
while (cur != null) {
// 临时存储好下一个节点以免丢失
Node next = cur.next;
// 当前节点等于前一个节点（翻转动作）
cur.next = pre;
// 当前节点成为前一个节点
pre = cur;
// 游标向下一个节点移动
cur = next;
}
// cur为空，pre则为原链表里最后一个节点，也就是翻转后链表的头结点
return pre;
}
}

翻转前n个节点

翻转前4个
link list：10 9 8 7 6 5 4 3 2 1
link list：7 8 9 10 6 5 4 3 2 1


/**
* reverse a part(nth) of a link list
* @author humorchen
* @date 2023/1/31 14:41
*/
public class ReversePartOfLinkList {
public static void main(String[] args) {
//生成链表
Node head = LinkListUtil.newList(10);
// 打印链表
LinkListUtil.print(head);
// 要翻转前多少个
int n = 4;
// 翻转处理
Node newHead = reverse(head, n);
// 打印翻转后的链表
LinkListUtil.print(newHead);
}
/**
* 翻转链表前n个节点
* @param head
* @param n
* @return
*/
static Node reverse(Node head, int n) {
// 特殊情况处理
if (head == null) {
return null;
}
// pre为上一个节点，cur为当前节点，是个游标
Node pre = null, cur = head;
// 当前节点不为空，且还需要翻转n个
while (cur != null && n > 0) {
// 提前存储游标下一个节点，以免操作时丢失
Node next = cur.next;
//
当前节点的next设置为前一个节点（翻转操作）
cur.next = pre;
// 当前节点成为pre节点
pre = cur;
// 当前游标节点cur向右移动
cur = next;
// 还需要翻转的个数自减
--n;
}
// 翻转后的前n个元素的子链表与切割处的节点进行拼接（cur已经到了翻转后的下一个节点了，head是翻转后链表的最后一个节点）
head.next = cur;
return pre;
}
}