题目描述
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
思考题：
- 请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。
样例
输入:1->2->3->4->5->NULL 输出:5->4->3->2->1->NULL
方法一：链表+迭代 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; } };
方法二：链表+递归 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; } };
欢迎大家在评论区交流~
