优雅的反转链表你知道吗
一、思路
1. 非递归。
1）不用栈。重复将首节点的下一个节点调整到最前面，如链表1->2->3->4，调整过程为2->1->3->4，3->2->1->4，4->3->2->1
2）使用栈。栈先进后出。将原链表的元素从头到尾入栈后，从栈顶到栈底的元素的顺序即为原链表反转后的顺序。
2. 递归。使链表从尾节点开始指向前一个节点。
二、代码
public class Solution {
//节点类
public static class Node {
//当value值为-1时，代表是虚拟头结点
int value;
Node next = null;
Node(int value) {
this.value = value;
}
}
/**
* 构建链表（递归）
* @param list 内容即是要构建的链表含有的元素
* @return 与list相同顺序的链表
*/
public static Node constructNodeListRecursive(List<Integer> list){
if (list.isEmpty()){
return null;
}
Node headNode = new Node(list.get(0));
// 子递归构建链表
Node tempNode = constructNodeListRecursive(list.subList(1, list.size()));
// 头结点指向子递归构建的链表头部
headNode.next=tempNode;
return headNode;
}
public static void main(String[] args) {
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
// 调用非递归方法（不用栈）
Node nodeList1 = constructNodeListRecursive(list);
Node resultNonRecursive = reverseLinkedListNonRecursive(nodeList1);
// 输出结果
dump(resultNonRecursive);
// 调用非递归方法（使用栈）
Node nodeList2 = constructNodeListRecursive(list);
Node resultRecursiveStack=reverseLinkedListNonRecursiveStack(nodeList2);
// 输出结果
dump(resultRecursiveStack);
// 调用递归方法
Node nodeList3 = constructNodeListRecursive(list);
Node resultRecursive=reverseLinkedListRecursive(nodeList3);
// 输出结果
dump(resultRecursive);
}
// 输出结果
public static void dump(Node head) {
if (null != head) {
Node temp=head;
while (null!=temp){
System.out.print(temp.value);
System.out.print(" ");
temp=temp.next;
}
System.out.println();
}
}
/**
* 非递归方法，不用栈
* @param head 头结点
* @return 链表反转过后的头结点
*/
public static Node reverseLinkedListNonRecursive(Node head){
if (head == null || head.next == null){
return head;
}
//构建一个虚拟头节点，用于翻转链表操作
Node p = new Node(-1);
p.next = head;
Node nextNode = head.next;
while (nextNode != null){
//后一个节点调整到前面
head.next = nextNode.next;
nextNode.next = p.next;
p.next = nextNode;
nextNode = head.next;
}
return p.next;
}
/**
* 非递归方法，使用栈（栈先进后出，天生就可以反转链表）
* @param head 头结点
* @return 链表反转过后的头结点
*/
public static Node reverseLinkedListNonRecursiveStack(Node head){
Stack<Node> nodeStack = new Stack<>();
Node temp = null;
//从头结点开始存入栈中
while (head != null){
nodeStack.push(head);
head = head.next;
}
//栈顶的元素即为链表原来的最后一个元素
if ((!nodeStack.isEmpty())){
temp = nodeStack.pop();
}
//栈中元素依次处理
while (!nodeStack.isEmpty()){
Node tempNode = nodeStack.pop();
tempNode.next.next=tempNode;
tempNode.next=null;
}
return temp;
}
/**
* 递归方法
* @param head 头结点
* @return 链表反转过后的头结点
*/
public static Node reverseLinkedListRecursive(Node head) {
// 子递归结束
if (head == null || head.next == null) {
return head;
}
// 获取去除头结点之外的链表反转后的头结点
Node pNode = reverseLinkedListRecursive(head.next);
head.next.next = head;
head.next = null;
return pNode;
}
}
致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。
若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。
