剑指offer面试题16:反转链表
2024-08-21 07:54:59
题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点。
解题思路:单向链表只能实现单向遍历,改变链表方向就是要把当前链表的节点指向它的前一个节点,
一旦当前链表指向发生了变化,就不能根据此节点获取到它后面的节点,所以在改变方向前要保存当前节点的下一节点,防止链表断开,
因此需要三个指针来保存当前节点,当前节点的前节点,当前节点的下节点。
注意:如果当前节点没有下一节点,则此节点就是反转后的链表的头结点。
另外一种解决办法是使用一个栈结构,顺序遍历链表,把每个节点依次入栈。待全部节点入栈后,依次把节点从栈中取出并连接,这样得到的链表也是反转后的链表。
package Solution; public class No16ReverseList { public static class ListNode {
int data;
ListNode next; public ListNode() { } public ListNode(int value, ListNode next) {
this.data = value;
this.next = next;
}
} public static ListNode reverseList(ListNode head) {
if (head == null)
throw new RuntimeException("invalid List,can't be null");
if (head.next == null)
return head;
ListNode reversedHead = null;
ListNode node = head;
ListNode preNode = null;
while (node != null) {
ListNode nextNode = node.next;
if (nextNode == null)
reversedHead = node;
// 赋值顺序不能变
node.next = preNode;
preNode = node;
node = nextNode;
}
return reversedHead;
} public static void print(ListNode head) {
if (head == null)
System.out.println("当前链表为空");
while (head != null) {
System.out.print(head.data + ",");
head = head.next;
}
} public static void main(String[] args) {
ListNode node1 = new ListNode(4, null);
ListNode node2 = new ListNode(3, node1);
ListNode node3 = new ListNode(2, node2);
ListNode node4 = new ListNode(1, node3); print(reverseList(node4));
System.out.println();
print(reverseList(new ListNode(5, null)));
System.out.println();
print(reverseList(new ListNode()));
System.out.println();
} }
最新文章
- FPGA 开发笔记 点滴
- mono 3.10.0 正式发布:性能进一步改进
- bootstrap 学习总结
- 随手记一次利用webbowser控件打开网页后cookie读取与设置
- 练习使用markdown编辑
- 消息中间件Notify和MetaQ-阿里中间件
- POJ 2069 Super Star
- HDU 1576 A/B(数论)
- 【转】国外程序员整理的Java资源大全
- 简单的sql调优(批处理)
- (七十四)iOS8之前使socket可以后台运行的方法
- idea配github
- UICollectionView 基础
- 日志分析工具 Log Parser
- CSS表单3 光标样式 (每个位置鼠标放上去的样式不同)
- Mysql插入中文的字段内容时乱码的解决方法
- docker容器中的peewee如何连接已有的容器中的数据库
- DbgPrint/KdPrint输出格式控制
- Python的网络编程 Socket编程
- std::bind
热门文章
- 用7ch中断例程完成jmp near ptr s指令的功能,用bx向中断例程传送转移位移。
- 《剑指Offer》第20题(Java实现):定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
- [转] spring framework体系结构及内部各模块jar之间的maven依赖关系
- 20175325 《JAVA程序设计》实验一 《JAVA开发环境的熟悉》实验报告
- win10jdk环境变量配置问题:'javac' 不是内部或外部命令,也不是可运行的程序 或批处理文件。
- Finance财务软件(引入业务系统凭证专题)
- java -关于包装类自动装箱与拆箱拓展+整形常量池
- TCP与UDP基本认识及区别
- spring jar包解读(转)
- 从零开始学java(二)类与对象