剑指Offer:反转链表【24】
2024-08-29 11:27:25
剑指Offer:反转链表
题目描述
输入一个链表,反转链表后,输出新链表的表头。
解题分析
首先在对链表进行节点互换、移动操作时,用到的最基本的工具就是指针。利用指针我们可以对链表节点进行变换操作,所以这道题最基本的一点是确定使用指针这一工具。
接下来,去思考用几个指针来解决问题:
对于一个指针来说,我们最多能做到的就是顺序遍历:
对于两个指针来说,我们可以做到对判断链表是否又环、取倒数第N个节点等操作。
如果要对单向链表进行位置变换的话,至少是三个指针,我们来分析一下这个问题:
首先我们指向相邻的前三个元素,如下:
我们让红色指针指向节点next为NULL(因为它将作为最后一个节点,所以next是null)。
橙色指针节点next指向红色指针节点。
接着三个节点平行向右移动一位。(注:如果我们只有两个指针的话,此时黄色指针所指的节点将无法跟踪,所以必须是三个节点)
我们让让橙色指针节点next指向红色指针节点
接着三个节点平行向右移动一位。
我们让让橙色指针节点next指向红色指针节点
所以我们往复的只有两个操作:
第一:将橙色指针指向元素的next指向红色指针。
第二:将三个指针平行向右移动一位。
当我们提炼出了往复的操作之后,代码就很简单了!
Java题解
public ListNode ReverseList(ListNode head) {
//[!] 参数合法性校验
if(head == null)
return null; //[0] 定义三个指针
ListNode ptr_pre = head;
ListNode ptr_cur = head.next;
if(ptr_cur==null)
return head;
ListNode ptr_next = ptr_cur.next; //[!] 第一个元素没有next
ptr_pre.next = null;
while (ptr_next!=null){
//[1] 切断然后重新连接
ptr_cur.next = ptr_pre; //[2] 向右移动
ptr_pre = ptr_cur;
ptr_cur = ptr_next;
ptr_next = ptr_next.next;
}
//[!] 最后一个元素的next指向他前面的一个
ptr_cur.next = ptr_pre;
return ptr_cur;
}
最新文章
- python和数据科学(Anaconda)
- 注解:【基于外键的】Hibernate双向1->;1关联
- Building good docker images
- uiautomator跑安卓端UI testing
- [LeetCode] Letter Combinations of a Phone Number
- Linux QtCreator设置mingw编译器生成windows程序
- 深入浅出ExtJS 第四章 表单与输入控件
- CentOS6.3连网获取IP失败 This device is not active
- STAD Parameters
- htmlcss笔记--a
- ajax 的基本原理
- Eclipse3.7中搭建Android开发环境文档教程和视频教程
- phpMyAdmin 完整路径泄露漏洞2
- 恢复SQLServer实例连接
- LInux ugo权限详解
- MySQL 的索引优化
- 【BZOJ3289】Mato的文件管理 莫队+树状数组
- Shell-2--输入输出重定向
- TP文件上传
- How to install Redis 3.2 on CentOS 6 and 7