侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【迭代, 递归】反转链表

GabrielxD
2022-06-21 / 0 评论 / 0 点赞 / 37 阅读 / 642 字 / 正在检测是否收录...

题目

206. 反转链表

剑指 Offer 24. 反转链表

剑指 Offer II 024. 反转链表


给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

image-20220622231356292

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

image-20220622231403854

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

解题

方法一:递归

思路

对于递归算法,最重要的就是明确递归函数的定义。具体来说,我们的 reverse 函数定义是这样的:
输入一个节点 head,将「以 head 为起点」的链表反转,并返回反转之后的头结点
明白了函数的定义,再来看这个问题。比如说我们想反转这个链表:

img

那么输入 reverse(head) 后,会在这里进行递归:

ListNode newHead = reverse(head.next);

不要跳进递归(你的脑袋能压几个栈呀?),而是要根据刚才的函数定义,来弄清楚这段代码会产生什么结果:

img

这个 reverse(head.next) 执行完成后,整个链表就成了这样:

img

并且根据函数定义,reverse() 函数会返回反转之后的头结点,我们用变量 newHead 接收了。
现在再来看下面的代码:

head.next.next = head;
img

接下来:

head.next = null;
return last;
img

神不神奇,这样整个链表就反转过来了!递归代码就是这么简洁优雅,不过其中有两个地方需要注意:

  1. 递归函数要有 base case,也就是这句:

    if (head == null || head.next == null) return head;
    

    意思是如果链表为空或者只有一个节点的时候,反转结果就是它自己,直接返回即可。

  2. 当链表递归反转之后,新的头结点是 newHead,而之前的 head 变成了最后一个节点,别忘了链表的末尾要置空:

    head.next = null;
    

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

方法二:迭代

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode curr = head, newNext = null, newPrev;
        while (curr != null) {
            newPrev = curr.next;
            curr.next = newNext;
            newNext = curr;
            curr = newPrev;
        }
        return newNext;
    }
}
0

评论区