leetcode:反转链表

题目描述

题目链接：206. 反转链表 - 力扣（LeetCode）

分析题目

思路一

我们可以设计算法让整个链表掉头

定义三个代码n1,n2,n3

n1指向NULL，n2指向head，n3指向第二个结点

当n2不为NULL的时候，让n2->next反方向指向n1，然后n1，n2，n3都往后移动

当n3走到NULL的时候，会出现空指针的问题，这个时候我们给n3单独加一个判断

if(n3!=NULL)，n3=n3->next

注意：我们没有交换值，而是改变了指针的指向

另外，当链表本身为空的时候，直接返回NULL，所以我们也需要加一个判断链表为空的条件

思路二

定义一个newhead指向NULL作为新链表的头，定义cur指向原链表的第一个结点，next保存第二个结点

然后将cur尾插，newhead作为新的头，cur走到原链表的第二个结点，next指向next->next

最后，当cur不为空的时候，则进入循环，为了防止next成为空指针，我们加一个判断：

if(next!=NULL)，则next=next->next

同样的，当链表本身为空的时候，直接返回NULL，所以我们也需要加一个判断链表为空的条件

代码示例

代码一

根据思路一，我们可以写出下面的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    struct ListNode* n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    free(n3);
    free(n2);
    return n1;
}

结果就通过了

代码二

根据思路二，我们可以写出下面的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* newhead=NULL;
    struct ListNode* cur=head;
    struct ListNode* next=cur->next;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        next=next->next;
    }
    free(next);
    free(cur);
    return newhead;
}

同样，结果也可以通过