leetcode：206. 反转链表

一、题目

 

函数原型：

struct ListNode* reverseList(struct ListNode* head)

二、思路

要对链表进行反转，可以有两种方法：

1.改变链表中每个结点之间的指针域指向，最后返回尾结点即可。

2.新建一个链表，将原链表中的结点依次头插到新链表中，最后返回新链表。

三、代码实现

代码1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)//空链表无需反转
    {
        return NULL;
    }
    else//设置三个遍历指针
    {
        struct ListNode *prev=NULL;//前指针，用于作为当前结点改变指向后的对象
        struct ListNode *cur=head;//当前指针
        struct ListNode *next=head->next;//后指针，用于当前指针改变指向后，保存其后一结点，防止丢失
        while(cur)
        {
            cur->next=prev;//将当前结点的指针域指向前一结点
            prev=cur;//前指针遍历
            cur=next;//当前指针遍历
            //后指针遍历，由于当前指针遍历到尾结点时，后指针指向空，因此后指针遍历时需要判断是否为空
            if(next)
                next=next->next;
            else
                next=NULL;
        }
        return prev;//最后前指针指向尾结点，直接返回前指针
    }
}

代码2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)//空链表，无需反转
    {
        return NULL;
    }
    else
    {
        struct ListNode *newhead=NULL;//新的头结点
        struct ListNode *cur=head;//遍历指针
        while(cur)
        {
            struct ListNode *next=cur->next;//先保存当前结点的下一结点
            cur->next=newhead;//头插的结点的指针指向头结点
            newhead=cur;//头插的结点成为新的头结点
            cur=next;//遍历指针移动
        }
        return newhead;//返回新的链表
    }
}