Java 单向链表翻转
2023-09-11 14:19:04 时间
链表翻转的思路有很多,再此做个记录。
思路一:最简单的思路就是先遍历链表,逐一将链表里的节点放入到栈里面;然后在遍历栈,将栈里的元素在逐一出栈形成新的链表。主要是利用了栈的后进先出的特点。
public static ListNode reverseListNodeByStack(ListNode node) {
Stack<ListNode> stack = new Stack<ListNode>();
ListNode head = node;
//链表入栈
while(head!=null) {
//当前要入栈的头部节点
ListNode currentHead=head;
//移动head指针,指向下一个节点
head=head.next;
//将当前头部节点的next设置为null,这样就单独将头部节点放入栈了,其子节点不会入栈
currentHead.next=null;
stack.push(currentHead);
}
ListNode newHead = stack.pop();
//新链表的next节点
ListNode currentNextNode=newHead;
//出栈构成新链表
while(!stack.isEmpty()) {
ListNode popNode = stack.pop();
currentNextNode.next=popNode;
currentNextNode=popNode;
}
return newHead;
}
思路二:
遍历链表,然后修改head.next的指向。每一次遍历都需要不断移动head指针 ,然后将新的head的next指向已经遍历过得节点就可以了:
/**
* 链表翻转
* @param node
*/
public ListNode reverseListNode(ListNode node) {
//新链表的头部节点,刚开始肯定是null
ListNode newHead = null;
ListNode head=node;
while (head != null) {
//当前需要处理的链表
ListNode oldHead= head;
//移动head,head.next指的是链表中未处理的部分
head = head.next;
//让链表的第一个元素指向已经翻转的链表
oldHead.next = newHead;
//将oldHead作为newhead的头部
newHead= oldHead;
}
//输出已完成翻转的链表
return newHead;
}
ListNode的代码如下,为了调试方便,特地重写了toString方法,用来打印链表的所有值:
public class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public String toString() {
String str=""+val;
ListNode temp = next;
while(temp!=null) {
str+=temp.val;
temp=temp.next;
}
return str;
}
}
相关文章
- java -version 问题 : C:ProgramDataOracleJavajavapath;
- java 锁2
- Java实现 LeetCode 382 链表随机节点
- Java实现 LeetCode 226 翻转二叉树
- java算法集训代码填空题练习3
- Java实现 蓝桥杯VIP 算法训练 猴子分苹果
- 【JAVA】MacBook安装Java环境及eclipse
- 【JAVA】java中的length和length()
- [Linux] Install java and add JAVA_HOME, PATH
- 请回答一下Java中有几种线程池及实现过程?
- Java //PP2.8 编写一个应用程序,以小时、分、秒读取时间长度,然后全部换算成秒并打印输出结果(例如,1小时28分42秒等于5322秒)
- Java 8 Lambda实现原理分析
- JAVA语言之Java 中不同的并行实现的性能比较
- Java内部类详解
- 【java】Java 中泛型的实现原理
- 【java】Java 多态
- java入门 常见问题0014:有get/set的属性建议设置为private,否则get/set可能失去作用