算法每日一题（反转单链表）C语言版

在本篇文章里，我将分享一道很经典的算法题———反转链表，并且分享多种方法去解决方法，希望可以帮助到你😀😀😀

反转链表_牛客题霸_牛客网

题目描述：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

​

示例1：

输入：{1,2,3}

返回值：{3,2,1}

示例2

输入：{} 返回值：{}

说明：空链表则输出空

以下代码均经过牛客测试，均正确，请放心测试😊😊😊

解法1：（迭代）

解题思路：

设

n1=NULL,n2=phead,n3=phead->head;

然后将链表的导向改变就可以进行链表的反转了👌

n3的作用是保存下一个地址，避免找不到后面的链表

​

代码：

struct ListNode* ReverseList(struct ListNode* head)
{
    struct ListNode *n1=NULL,*n2=head,*n3=head->next;
    if(head==NULL&&head->next==NULL)
    return NULL;
    else
    {
        while(n2)
        {
            n2->next=n1;//反转
            //迭代
            n1=n2;
            n2=n3;
            if(n3!=NULL)
            n3=n3->next;
        }
        return n1;
    }
}

结果展示：

​

解法2：（头插）

解题思路：

再设一个链表B，利用链表的头插法将原链表头插到链表B上，继而return 链表B即可

代码：

struct ListNode* ReverseList(struct ListNode* head)
{
    struct ListNode *cur=head,*next=head->next,*newhead=NULL;
    while(cur!=NULL)
    {
        next=cur->next;
        //头插
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;
}

结果展示：

​

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：

> 1.做==更好的自己==，而不是完美的别人。

> 2.谁都愿意做自己喜欢的事情，可是，做你该做的事情，才叫成长。

> 3.活成一个真正有形的人，而不是—摊肉、一团混乱不堪的情绪。

> 4.放弃很容易，但坚持—定很酷。

> 5.知识不是力量，知识用起来才是力量。

> 6.人生只有两个选择，要么忙着死，要么忙着活! ==熬得住就出众，熬不住就出局==，你的野心很大，所以没资格停下。

最后如果觉得我写的还不错，请不要忘记点赞✌，收藏✌，加关注✌哦(｡･ω･｡)

**愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚==菜鸟==逐渐成为==大佬==。加油，为自己点赞！**

​