剑指offer 23. 反转链表

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

• 请同时实现迭代版本和递归版本。

数据范围

链表长度 [0,30]。

样例

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

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

方法一：链表+迭代 O(n)

直接设置三个指针分别指向前一个结点，当前结点和下一个结点，然后进行相应操作。我们拿题目的样例举例，来看看具体的实现步骤：

第一步： 设置 cur 和 prev 指针，分别指向头结点和 NULL 。

第二步： 得到 nxt 指针，然后将 nxt 指向的结点的 next 指针指向 cur 指向的结点，将 cur 指向的结点的 next 指针指向 prev 的所指。

第三步： 将 prev 指针更新为 cur 所指，将 cur 指针更新为 nxt 所指，然后重复第二步操作。以此类推，直至 cur 为空。

第四步： 得到最终链表，直接返回即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* prev = NULL;
        while (cur)
        {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二：链表+递归 O(n)

递归做法其实就是一直递归到底，递归到最后一个结点然后开始回溯，在回溯的过程中改变结点的指针指向。我们还是拿题目样例举例，看看是如何实现的：

第一步： 一直往后递归，直至最后一个结点位置。

第二步： 开始回溯，每次回溯时都去改变当前结点的指针指向，将当前结点的下一个结点的 next 指针指向自己，然后将自己的 next 指针置空，指针返回第一个结点。

第三步： 返回最终链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

欢迎大家在评论区交流~