题解 | #反转链表#

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

#include <stdlib.h>
// void insert(struct ListNode** link,struct ListNode** temp){
//     if((*link)==NULL){
//         (*link)=（*temp）;
//     }
//     else{
//         （*temp）->next =(*link);
//         (*link)=（*temp）;
//     }

// }

// struct ListNode* ReverseList(struct ListNode* pHead ) {
//     // write code here
//     struct ListNode* new =NULL;

//     while (pHead) {
//         struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
//         temp->val=pHead->val;
//         temp->next =NULL;
//         insert(&new,&temp);
//     }
//     return new;

// }

struct ListNode* ReverseList(struct ListNode* pHead) {
    struct  ListNode* pre = NULL;
    struct  ListNode* cur = pHead;
    struct ListNode* nex = NULL; // 这里可以指向NUll，循环里面要重新指向
    while (cur) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    return pre;
}

法1：遍历链表，同时利用头插法建立一个新链表，最后返回新链表即可；但空间复杂度为O(n)，不符合题意；

法2：三指针法， nex = cur->next; cur->next = pre; pre = cur; cur = nex;，遍历一遍即可，空间空间复杂度为O(1)