题目描述

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

思考题：

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

样例

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

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

代码&思路

迭代做法

/**
 * 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;//最后将最后的结果的尾结点指向NULL
        return a;//返回尾结点，因为b到最后指向的应该是NULL，所以尾结点是a
    }
};

递归做法

/**
 * 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 tail=reverseList(head->next);//链表的最后一个元素
        head->next->next=head;//将头结点的下一个结点的next指向头结点(因为头街点没有被翻转)
        head->next=NULL;//将头结点指向空
        return tail;
    }
};