力扣206. 反转链表

题目描述：

反转一个单链表。

示例:

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

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

 

方法1：逆方向-迭代

//逆方向-迭代

typedef struct ListNode Node;

struct ListNode* reverseList(struct ListNode* head){

    //如果头节点为空，或者只有一个头节点没有其他结点

    //return head就行

    if(head==NULL||head->next==NULL)

        return head;

    //定义三个指针：n1,n2,n3;

    //开始时分别指向NULL,head,head->next;

    Node*n1=NULL,*n2=head,*n3=head->next;

    //终止条件是n1指向最后一个节点，n2,n3指向NULL

    //所以循环控制条件是n2!=NULL

    //即while(n2)

    while(n2)

    {

        //反转

        n2->next=n1;

        //迭代

        n1=n2;

        //n3给n2要加判断条件

        //如果n3已经指向NULL，就不能把NULL给n2

        n2=n3;

        if(n3)

            n3=n3->next;

    }

    return n1;

}

方法2：头插法

//头插法

typedef struct ListNode Node;

//不需要像逆方向-迭代一样

//if(head==NULL||head->next==NULL)

//  return head;

//如果是空节点

//cur=head=NULL;

//while(cur)循环就进不去

//最后return newhead=NULL;

//如果只有一个节点，拿下来头插就可以

struct ListNode* reverseList(struct ListNode* head){

    //定义三个指针newhead cur next;

    //其中newhead是新链表，cur,next在老链表里

    //分别指向NULL,head,cur->next;

    Node*newhead=NULL,*cur=head;

    //终止条件是cur指向NULL

    //所以循环控制条件是cur!=NULL

    //即while(cur)

    while(cur)

    {

        //一旦把cur指向的元素往新链表里去放

        //cur和cur->next就失去联系了

        //所以需要定义next=cur->next;

        //这个next=cur->next应该放在循环里，并且在头插之前

        Node*next=cur->next;

        //头插

        //在新链表里，cur->next=newhead

        //第一次cur指向NULL

        //以后每次cur放到新链表里要指向上次的最后一个节点

        cur->next=newhead;

        //在新链表里，把cur给newhead;

        newhead=cur;

        //在老链表里，为了使cur和next继续往后走

        cur=next;

    }

    //最后返回新链表的头节点就可

    return newhead;

}