反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路迭代(麻烦版)

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* temp=head;
    struct ListNode* c=head;
    struct ListNode* reverse=head;
    if(head==NULL){
        return NULL;
    }
    int count=1;
    while(c->next!=NULL){
        count++;
        c=c->next;
    }
    
    int i=0;
    int a[count];
    while(temp!=NULL){
        a[i]=temp->val;
        i++;
        temp=temp->next;
    }
    
    for(int j=count-1;j>=0;--j){
        reverse->val=a[j];
        reverse=reverse->next;
        
    }
    return head;
}

思路迭代(简洁)

1->2 反转该链表，1的下一节点应指向NULL，事先需要用temp先保存2，这时新头节点newHead为1，下一循环，然后针对节点2做同样操作，2的下一节点为NULL，接着设为节点1

struct ListNode* reverseList(struct ListNode* head) {
    
    struct ListNode* node=head;
    struct ListNode* newHead=NULL;
    struct ListNode* temp=NULL;
        
    while(node!=NULL){
        temp=node->next;
        node->next=newHead;
        newHead=node;
        node=temp;
    }
    return newHead;
 }

递归

先反转后面的链表，从最后面的两个结点开始反转，依次向前，将后一个链表结点指向前一个结点，注意每次反转后要将原链表中前一个结点的指针域置空

struct ListNode* reverseList(struct ListNode* head) {
    //如果链表为空或者链表中只有一个元素
    if(head==NULL||head->next==NULL){
        return head;
    }
 //先反转后面的链表，直到链表的末端结点
    struct ListNode* temp=reverseList(head->next);
//再将当前节点设置为后面节点的后续节点
    head->next->next=head;
    head->next=NULL;
    return temp;
}