WangBa's Blog

0206. Reverse Linked List

LeetCode真的难系列

发布于：2020年10月9日
次浏览

206. 反转链表 Easy

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

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

解析

写链表的代码题，一定要考虑周全，可以从以下几个方面考虑：

  • 是否为空链表

  • 是否只剩一个结点

  • 剩余两个结点怎么样

  • 在处理头结点和尾结点时，逻辑上是否可以通过

迭代解法：

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
     // 迭代法
    ListNode pre = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

这就是在链表中说到的哨兵，这样最大的目的就是为了让对整个链表的操作进行统一化

递归解法：

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
    // 递归法
    if (head == null || head.next == null) {
        return head;
    }
    ListNode listNode = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return listNode;
}

在进行递归操作中，一定要注意的点：出口

也就是说一定要有最小条件，而这个条件是可以跳出最后一个递归调用的，然后将结果放到倒数第二个递归调用中

在这里面出口就是：

1
2
3
if (head == null || head.next == null) {
    return head;
}

一旦满足这个条件，就可以触发所有递归调用的结束

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/10/09/0206-Reverse-Linked-List/

更新于：2020年10月9日

Leetcode

Array

LinkedList

评论