算法leetcode

力扣206-反转链表

字数统计: 787字   |   阅读时长: 3分
, ,

摘要: 面试最爱问的反转链表，迭代和递归

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来看一下面试当中非常爱问的反转链表，当你去面试别人不知道问什么题的时候，就问反转链表总是不容易出错的。本题在力扣上虽然是简单题，但是考察了数据结构的维护、迭代、递归等基本的编程思想，

题目

206. 反转链表

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

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

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

示例 3：
输入：head = []
输出：[]

提示：

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

题解

算法1：递归

如果 reverseList(iter) 将链表从 iter 节点到末尾这一段反转并返回新链表的表头。那么我们可以递归第地先把链表从 iter -> next 节点到末尾这一段，也就是 iter 之后的部分反转，然后返回反转后的新链表的表头 result。那么此时只需要再把新链表的末尾节点（也就是 iter -> next）连接到当前节点（也就是 iter），然后再返回 result 即可。我们要求的就是 reverseList(head)。递归过程中注意不要忘了将 iter 的 next 指针连接到 iter 的上一个节点，如图：

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 空链表
        if(head == nullptr) 
            return head;
        // 只有一个元素的链表
        if(head -> next == nullptr) 
            return head;

        // 至少两个元素，iter 初始为第二个
        ListNode *iter = head -> next;
        head -> next = nullptr;
        ListNode *result = reverseList(iter);
        iter -> next = head;
        return result;
    }
};

算法2：迭代

迭代的方法比较直接，就是用 iter 将链表上所有的节点按顺序走一遍。迭代过程中同时维护一个指针 next，指向原链表总 iter 节点后面的那个节点。迭代到 iter 节点时，将 next -> next 连接到 iter 节点，然后将 iter 和 next 整体像后移一个节点。如图。只要 iter -> next 节点非空，就继续迭代下去。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)
            return nullptr;
        ListNode* iter = nullptr;
        ListNode* nxt = head;
        while(nxt)
        {
            ListNode* tmp = nxt -> next;
            nxt -> next = iter;
            iter = nxt;
            nxt = tmp;
        }
        return iter;
    }
};

算法3：尾递归

在迭代算法中，我们需要维护 iter 和 nxt 这两个变量。每迭代一次，iter 和nxt 都向前推进一个元素。因此可以设计尾递归函数，包含 iter 和 nxt 这两个参数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)
            return nullptr;
        ListNode* iter = nullptr;
        ListNode* nxt = head;
        return _reverseList(iter, nxt);
    }

    ListNode* _reverseList(ListNode* iter, ListNode* nxt)
    {
        if(!nxt)
            return iter;
        ListNode* tmp = nxt -> next;
        nxt -> next = iter;
        return _reverseList(nxt, tmp);
    }
};
Share