每天一算:Reverse Linked List

LeetCode上第206号问题:Reverse Linked List

题目

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

解题思路

设置三个节点precurnext

  • (1)每次查看cur节点是否为NULL,如果是,则结束循环,获得结果

  • (2)如果cur节点不是为NULL,则先设置临时变量nextcur的下一个节点

  • (3)让cur的下一个节点变成指向pre,而后pre移动curcur移动到next

  • (4)重复(1)(2)(3)

动画演示

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

每天一算:Reverse Linked List
动画演示

参考代码

1.迭代的方式处理

每天一算:Reverse Linked List

2.递归的方式处理

 1// 206. Reverse Linked List
2// https://leetcode.com/problems/reverse-linked-list/description/
3//
4// 递归的方式反转链表
5// 时间复杂度: O(n)
6// 空间复杂度: O(1)
7class Solution {
8public:
9    ListNode* reverseList(ListNode* head) {
10
11        // 递归终止条件
12        if(head == NULL || head->next == NULL)
13            return head;
14
15        ListNode* rhead = reverseList(head->next);
16
17        // head->next此刻指向head后面的链表的尾节点
18        // head->next->next = head把head节点放在了尾部
19        head->next->next = head;
20        head->next = NULL;
21
22        return rhead;
23    }
24};



每天一算:Reverse Linked List


每天一算:Reverse Linked List

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 每天一算:Reverse Linked List

我还会在以下平台发布内容

GitHub 哔哩哔哩