PPT动画之每天一算：Reverse Linked List

旧城等待， 2023-06-13 09:11 2阅读 0赞

![v2-1c8c558460d7eefc705b098526843ffa\_b.jpg][v2-1c8c558460d7eefc705b098526843ffa_b.jpg]

LeetCode上第206号问题：**[Reverse Linked List][]**

> 反转一个单链表。  
>   
> **示例:**  
> 输入: 1->2->3->4->5->NULL  
> 输出: 5->4->3->2->1->NULL  
>   
> **进阶:**  
> 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

## **思路** ##

设置三个节点`pre`、`cur`、`next`

*  （1）每次查看`cur`节点是否为`NULL`，如果是，则结束循环，获得结果
 *  （2）如果`cur`节点不是为`NULL`，则先设置临时变量`next`为`cur`的下一个节点
 *  （3）让`cur`的下一个节点变成指向`pre`，而后`pre`移动`cur`，`cur`移动到`next`
 *  （4）重复（1）（2）（3）

## **动画演示** ##

**动画演示GIF有点大，请稍微等待一下加载显示^\_^**

![v2-c434ed3a1a229820ae04b07f26896d32\_b.gif][v2-c434ed3a1a229820ae04b07f26896d32_b.gif]

## **代码** ##

## **迭代的方式处理** ##

// 206. Reverse Linked List
    // https://leetcode.com/problems/reverse-linked-list/description/
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
    
            ListNode* pre = NULL;
            ListNode* cur = head;
            while(cur != NULL){
                ListNode* next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
    
            return pre;
        }
    };

## **递归的方式处理** ##

// 206. Reverse Linked List
    // https://leetcode.com/problems/reverse-linked-list/description/
    //
    // 递归的方式反转链表
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
    
            // 递归终止条件
            if(head == NULL || head->next == NULL)
                return head;
    
            ListNode* rhead = reverseList(head->next);
    
            // head->next此刻指向head后面的链表的尾节点
            // head->next->next = head把head节点放在了尾部
            head->next->next = head;
            head->next = NULL;
    
            return rhead;
        }
    };

## **执行结果** ##

![v2-aa30de8408a632ec412461fa1346d40c\_b.jpg][v2-aa30de8408a632ec412461fa1346d40c_b.jpg]

![v2-eef63e32a520d47e999778ee523a2230\_b.jpg][v2-eef63e32a520d47e999778ee523a2230_b.jpg]

[v2-1c8c558460d7eefc705b098526843ffa_b.jpg]: https://img-blog.csdnimg.cn/img_convert/7b0d67d1e15f8a2753f4cc7f4691c148.png
[Reverse Linked List]: https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/reverse-linked-list/
[v2-c434ed3a1a229820ae04b07f26896d32_b.gif]: https://ss.csdn.net/p?https://pic3.zhimg.com/v2-c434ed3a1a229820ae04b07f26896d32_b.gif
[v2-aa30de8408a632ec412461fa1346d40c_b.jpg]: https://img-blog.csdnimg.cn/img_convert/59f21da25e1503626b663c210dfc1dec.png
[v2-eef63e32a520d47e999778ee523a2230_b.jpg]: https://img-blog.csdnimg.cn/img_convert/67b6e3d8301500c40d2814ef2acf88f6.png