题目描述

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

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

样例

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

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

迭代版本

思想

将指针a、b指向的两个节点之间的指针指向反向；在让指针a、b向后移动

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;//因为反转，最后原来的头节点为尾节点，next要设为空值

        return a;
    }
};

递归版本

C++ 代码

//  迭代版本
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)    //如果只有一个节点，或者没有节点，直接返回
            return head;

        auto tail = reverseList(head->next);//返回反转完链表的头节点，也是整个链表的头结点

        head->next->next = head;//即让反转完链表的尾节点指向头结点，然后next置NULL
        head->next = NULL;

        return tail;
    }
};