一、问题

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：

二、代码

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 *
 * @param pHead ListNode类
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    int arr[1001];
    struct ListNode* tmp = pHead;
    int i = 0;
    while (tmp != NULL) {
        arr[i] = tmp->val;
        i ++;
        tmp = tmp->next;
    }
    if (i <= 0) {
        return pHead;
    } 
    // return pHead;
    else {
        struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
        head->val = arr[i - 1];
        struct ListNode* tmp = head;
        for (int j = i - 2; j >= 0; j --) {
            struct ListNode* n = (struct ListNode*)malloc(sizeof(struct ListNode));
            n->val = arr[j];
            tmp->next = n;
            tmp = n;
        }
        return head;
    }
}

三、总结

别忘了为节点分配空间