XTAO's Tech Blog
0%

[Leetcode]206. Reverse Linked List(C++)

发表于 更新于 分类于 ， 评论数：
1.7k 2 分钟

题目描述

题目链接：206. Reverse Linked List

Reverse a singly linked list.

例子

例子 1

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow Up

A linked list can be reversed either iteratively or recursively. Could you implement both?

解题思路

如题所述，这道题有两种思路：迭代或者递归，迭代比较简单，递归要注意的点稍微多一点。

迭代法

迭代法主要考虑维护三个节点间的关系：前一个节点（previous）、当前节点（current）、下一节点（next）。对于这三个节点，我们要做的是：

  • 存储下一节点，如果不事先做备份，一旦我们更新 current->next，那么下一节点就丢失了
  • 更新 current->next 使其指向前一节点
  • 分别更新 previous 和 current 为 current 和 next，然后重复以上操作

另外注意一些基本例子的操作，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        method #1: iteratively
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }

        return prev;

};

递归法

递归法直观上比较好理解：假定我们有一个递归函数 func，函数逆转给定链表并返回链表尾端节点，那我们要做的是：

  • 给定 head，判断如果是空节点或者单节点链表，无须逆转，直接返回 head
  • 否则先逆转后面链表并让其返回的节点指向当前节点，即 func(head->next)->next = head

但是题目要求我们需要返回新链表的头部节点，因此我们需要在递归函数中进行判断，传入一个链表节点指针的引用 new_head（注意是引用，不能是链表节点，否则内部改变链表节点不会影响外部节点），但当前给定的链表是空或者单节点链表时表示已经在进行最后一个节点的逆转，新链表的节点应该是当前节点，对 new_head 进行更新即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        if (head == nullptr) return head;

        ListNode* new_head = new ListNode();
        reverseListRecursivly(head, new_head);
        head->next = nullptr;

        return new_head;
    }

private:
    ListNode* reverseListRecursivly(ListNode* head, ListNode*& new_head) {
        
        if (head == nullptr || head->next == nullptr) {
            new_head = head;
            return head;
        }
        
        reverseListRecursivly(head->next, new_head)->next = head;

        return head;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址： 206.ReverseLinkedList.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章