链表之单链表的反转总结
【摘要】 单链表的反转是常见的面试题目。本文总结了2种方法。
1 定义
单链表node的数据结构定义如下：
class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; }}
2 方法1：就地反转法
2.1 思路
把当前链表的下一个节点pCur插入到头结...
单链表的反转是常见的面试题目。本文总结了2种方法。
1 定义
单链表node的数据结构定义如下：
-
class ListNode {
-
int val;
-
ListNode next;
-
ListNode(int x) {
-
val = x;
-
next = null;
-
}
-
}
2 方法1：就地反转法
2.1 思路
把当前链表的下一个节点pCur插入到头结点dummy的下一个节点中，就地反转。
dummy->1->2->3->4->5的就地反转过程：
dummy->2->1->3->4->5 dummy->3->2->1->4->5 dummy->4>-3->2->1->5 dummy->5->4->3->2->12.2 解释
1初始状态
2 过程
pCur是需要反转的节点。
- prev连接下一次需要反转的节点
- 反转节点pCur
- 纠正头结点dummy的指向
- pCur指向下一次要反转的节点
伪代码
-
1 prev.next = pCur.next;
-
2 pCur.next = dummy.next;
-
3 dummy.next = pCur;
-
4 pCur = prev.next;
3 循环条件
pCur is not null
2.3 代码
-
// 1.就地反转法
-
public ListNode reverseList1(ListNode head) {
-
if (head == null)
-
return head;
-
ListNode dummy = new ListNode(-1);
-
dummy.next = head;
-
ListNode prev = dummy.next;
-
ListNode pCur = prev.next;
-
while (pCur != null) {
-
prev.next = pCur.next;
-
pCur.next = dummy.next;
-
dummy.next = pCur;
-
pCur = prev.next;
-
}
-
return dummy.next;
-
}
2.4 总结
- 1个头结点，2个指针，4行代码
- 注意初始状态和结束状态，体会中间的图解过程。
3 方法2：新建链表，头节点插入法
3.1 思路
新建一个头结点，遍历原链表，把每个节点用头结点插入到新建链表中。最后，新建的链表就是反转后的链表。
3.2 解释
1 初始状态
2 过程
pCur是要插入到新链表的节点。
pNex是临时保存的pCur的next。
- pNex保存下一次要插入的节点
- 把pCur插入到dummy中
- 纠正头结点dummy的指向
- pCur指向下一次要插入的节点
伪代码
-
1 pNex = pCur.next
-
2 pCur.next = dummy.next
-
3 dummy.next = pCur
-
4 pCur = pNex
3 循环条件
pCur is not null
3.3 代码
-
// 2.新建链表,头节点插入法
-
public ListNode reverseList2(ListNode head) {
-
ListNode dummy = new ListNode(-1);
-
ListNode pCur = head;
-
while (pCur != null) {
-
ListNode pNex = pCur.next;
-
pCur.next = dummy.next;
-
dummy.next = pCur;
-
pCur = pNex;
-
}
-
return dummy.next;
-
}
3.4 总结
- 1个头结点，2个指针（包含一个临时保存节点的pNex），4行代码
- 注意初始状态和结束状态，体会中间的图解过程。
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/50302665
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）