0


算法每日一题(反转单链表)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.人生只有两个选择,要么忙着死,要么忙着活! ==熬得住就出众,熬不住就出局==,你的野心很大,所以没资格停下。 **

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

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


本文转载自: https://blog.csdn.net/m0_68865259/article/details/127115475
版权归原作者 云小逸 所有, 如有侵权,请联系我们删除。

“算法每日一题(反转单链表)C语言版”的评论:

还没有评论