给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2] 输出:[2,1]
示例 3:
输入:head = [] 输出:[]
提示:
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
思路
如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:
之前链表的头节点是元素1, 反转之后头结点就是元素5 ,这里并没有添加或者删除节点,仅仅是改变next指针的方向。
那么接下来看一看是如何反转的呢?
我们拿有示例中的链表来举例
首先定义一个cur指针,指向头结点,再定义一个pre指针,初始化为null。
然后就要开始反转了,首先要把 cur->next 节点用tmp指针保存一下,也就是保存一下这个节点。
为什么要保存一下这个节点呢,因为接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。
接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。
最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。
Java:
// 双指针
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next;// 保存下一个节点
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
// 递归
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
private ListNode reverse(ListNode prev, ListNode cur) {
if (cur == null) {
return prev;
}
ListNode temp = null;
temp = cur.next;// 先保存下一个节点
cur.next = prev;// 反转
// 更新prev、cur位置
// prev = cur;
// cur = temp;
return reverse(cur, temp);
}
}
// 从后向前递归
class Solution {
ListNode reverseList(ListNode head) {
// 边缘条件判断
if(head == null) return null;
if (head.next == null) return head;
// 递归调用,翻转第二个节点开始往后的链表
ListNode last = reverseList(head.next);
// 翻转头节点与第二个节点的指向
head.next.next = head;
// 此时的 head 节点为尾节点,next 需要指向 NULL
head.next = null;
return last;
}
}
使用虚拟头结点解决链表翻转
使用虚拟头结点,通过头插法实现链表的翻转(不需要栈)文章来源:https://www.toymoban.com/news/detail-593715.html
// 迭代方法:增加虚头结点,使用头插法实现链表翻转
public static ListNode reverseList1(ListNode head) {
// 创建虚头结点
ListNode dumpyHead = new ListNode(-1);
dumpyHead.next = null;
// 遍历所有节点
ListNode cur = head;
while(cur != null){
ListNode temp = cur.next;
// 头插法
cur.next = dumpyHead.next;
dumpyHead.next = cur;
cur = temp;
}
return dumpyHead.next;
}
使用栈解决反转链表的问题
- 首先将所有的结点入栈
- 然后创建一个虚拟虚拟头结点,让cur指向虚拟头结点。然后开始循环出栈,每出来一个元素,就把它加入到以虚拟头结点为头结点的链表当中,最后返回即可。
public ListNode reverseList(ListNode head) {
// 如果链表为空,则返回空
if (head == null) return null;
// 如果链表中只有只有一个元素,则直接返回
if (head.next == null) return head;
// 创建栈 每一个结点都入栈
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 创建一个虚拟头结点
ListNode pHead = new ListNode(0);
cur = pHead;
while (!stack.isEmpty()) {
ListNode node = stack.pop();
cur.next = node;
cur = cur.next;
}
// 最后一个元素的next要赋值为空
cur.next = null;
return pHead.next;
}
采用这种方法需要注意一点。就是当整个出栈循环结束以后,cur正好指向原来链表的第一个结点,而此时结点1中的next指向的是结点2,因此最后还需要cur.next = null
文章来源地址https://www.toymoban.com/news/detail-593715.html
到了这里,关于力扣206. 反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!