注意点,迭代版本:退出循环的条件;递归:传入函数的变量
题目描述
定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
思考题:
请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。
样例
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL
c++
/**
* 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;
auto a = head, b = a->next;
while(b){
auto c = b->next;
b -> next = a;
a = b, b = c;
}
head -> next = NULL;
return a;
//递归
if(!head || !head -> next) return head;
//cout << head << endl;
auto tail = reverseList(head->next); //递归倒着退,输入函数是是head->next,函数参数是head
head -> next -> next = head; //head->next就是后面的节点
head ->next = NULL;
return tail; //tail一直是尾巴,倒序的头
}
};