1. 单向链表反转
1.1 题目要求
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例1:
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例2:
输入：head = [1,2]
输出：[2,1]
示例3:
输入：head = []
输出：[]
1.2 思路分析
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
1.3 关键代码
/**
* 单向节点
*/
public class SinglyNode {
public int val;
/**
* 下一个节点
*/
public SinglyNode next;
public SinglyNode(int val) {
this.val = val;
}
public SinglyNode(int val, SinglyNode next) {
this.val = val;
this.next = next;
}
}
/**
* 单向链表反转
* @param head 头节点
* @return
*/
public static SinglyNode reverseSinglyList(SinglyNode head) {
SinglyNode pre = null; // 当前节点的前一个节点,默认是null
SinglyNode next = null; // 当前节点的下一个节点,默认是null
while (head != null) {
next = head.next; // 获取当前节点的下一个节点
head.next = pre; // 当前节点的前一个节点变成当前的下一个节点(方向反转)
pre = head; // 当前节点赋值给pre,指针后移
head = next; // 指针移动到next节点,继续循环
}
return pre; // 最后头节点的引用
}2. 双向链表反转
2.1 关键代码
/**
* 双向链表节点
*/
public class DoubleListNode {
public int value;
/**
* 前一个节点
*/
public DoubleListNode last;
/**
* 下一个节点
*/
public DoubleListNode next;
public DoubleListNode(int value) {
this.value = value;
}
}
/**
* 双向链表反转
* @param head 头节点
* @return
*/
public static DoubleListNode reverseList(DoubleListNode head) {
DoubleListNode last = null; // 前一个节点
DoubleListNode next = null; // 下一个节点
while (head != null) {
next = head.next; // 获取当前节点的下一个节点
head.next = last; // 前一个节点变成当前节点的下一个节点(链表方向反转)[原来头节点的last节点为空,反转后在链表末尾,next节点为空]
head.last = next; // 下一个节点变成当前节点的前一个节点(方向反转)[原链表末尾节next节点为空,反转后变成头节点,last节点为空]
last = head; // 当前节点变成前一个节点,指针后移
head = next; // 指针指向下一个节点,进入下一轮循环.
}
return last; // 返回反转后的头节点的引用
}转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 george_95@126.com