题目描述

题目链接

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

1
2
3
4
示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2
3
4
示例 2：

输入：head = [1,2]
输出：[2,1]
1
2
3
4
示例 3：

输入：head = []
输出：[]

算法1

(迭代) O(n)O(n)

从头结点开始，两个一组翻转，将后一个节点的next指针指向其前一个几点，随后迭代进行

当后节点为空时，说明整个链表已经反转结束
调整头结点的next指针为空即可

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
27
28
29
/** 
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

 // 迭代版本
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return head;
        auto a = head, b = head->next;
        while( b)
        {
            auto t = b->next;
            b->next = a;
            a = b;
            b = t;
        }

        head->next = NULL;
        return a;
    }
};

算法1

(递归) O(n)O(n)

直接采用递归的思想：reverseList 函数实现的功能是将给定的链表翻转并返回反转后的头结点

那么我们可以将原链表头结点之后的节点翻转，再将原头结点接到反转后的头结点尾部即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

 // 递归版
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;

        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;

        return tail;
    }
};