题目描述

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

迭代版

通过数组记录链表中的值，反向输出数组给链表赋值，不需要对数组进行反转

/**
 * 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) {
        auto cur=head;
        int nums[31];
        int i=0;
        while(cur){
            nums[i++]=cur->val;
            cur=cur->next;
        }

        cur=head;
        while(cur){
            cur->val=nums[--i];
            cur=cur->next;
        }

        return head;
    }
};

递归版

一定要创建新的头结点

/**
 * 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) {
        auto cur=head;
        if(!cur||!cur->next)return cur;
        auto newNode=reverseList(cur->next);
        cur->next->next=cur;
        cur->next=NULL;

        return newNode; `` 
    }
};