辽宁网站建设价格,新闻发布的网站,销售方案网站,价格网打不开 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录链表OJ题(四)1. 反转… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 文章目录链表OJ题(四)1. 反转链表思路一 迭代法一、一般情况二、极端情况1.传入的链表为空时2.反转第一个结点指针的指向时3.反转最后一个结点指针的指向时思路二 头插法2.总结上一篇链表OJ题链接【链表OJ题(三)】链表中倒数第k个结点
链表OJ题(四)
1. 反转链表
链接206. 反转链表 描述 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例1 输入head [1,2,3,4,5] 输出[5,4,3,2,1] 示例2 输入head [1,2] 输出[2,1] 示例3 输入head [] 输出[] 思路一 迭代法
反转一个单向链表可以看成是将链表中的每个结点的指向反向即从后一个结点指向前一个结点我们在考虑情况的时候还是可以先考虑一般情况再考虑极端情况。
一、一般情况
要使两个结点之间的指针指向反转看似用两个变量足矣直接让后一个结点指向前一个结点。但是仔细思考后发现并没有那么简单我们如果直接让后一个结点指向前一个结点那么后一个结点所指向的再后面一个结点的位置就无从知晓了。所以我们还得定义3个指针变量n1n2n3
n1记录指针指向将要反转的结点反转后要指向的位置。 n2记录指针指向将要反转的结点。 n3记录指针指向将要反转的结点的下一个结点。 在反转时首先让n2指向的结点指向n1指向的位置
然后让n1n2n3指针统一后移准备执行下一对结点之间指向的反转。 如此进行下去所有的结点指向都将反转。
二、极端情况
极端情况也就是反转第一个结点指针的指向和反转最后一个结点指针的指向以及传入的链表为空时的情况。
1.传入的链表为空时
我们可以发现若传入的链表为空那么我们根本就不需要对链表进行任何操作直接返回传入的头指针即可。如果再稍加思考当传入链表只有一个结点时我们也不需要对链表进行任何操作直接返回传入的头指针也没问题。
2.反转第一个结点指针的指向时
因为n2记录的是指针指向将要反转的结点所以当反转第一个结点指针的指向时n2指针便指向的是第一个结点。
因为在我们反转过程中就是让n2指向的结点指向n1指向的位置所以我们只需将n1的初始值赋值为NULL即可。这样反转后就让第一个结点指针指向NULL了即反转后的最后一个结点指向空。
3.反转最后一个结点指针的指向时
当最后一个结点的指针指向被反转时n2刚好指向最后一个结点
在指针反转完成后n1n2n3指针统一向后移动位置如下
我们可以发现逻辑上是没有问题的而且此时也发现了遍历链表时的终止条件和需要返回的新的头指针即当n2指针为NULL时停止遍历并且返回n1指针指向的位置。 注意 这时这3个指针统一后移时n3指针的后移将失败因为n3后移前指向的是NULL我们不能执行以下这句代码
n3 n3-next;所以我们后移n3指针前需判断其是否为空。
代码实现
struct ListNode {int val;struct ListNode *next;
};struct ListNode* reverseList(struct ListNode* head)
{if (head NULL || head-next NULL)//当链表为空或只有一个结点时无需操作return head;//直接返回struct ListNode* n1 NULL;//记录指针指向将要反转的结点反转后要指向的位置。struct ListNode* n2 head;//记录指针指向将要反转的结点。struct ListNode* n3 head-next;//记录指针指向将要反转的结点的下一个结点。while (n2)//n2为NULL时停止遍历{n2-next n1;//反转结点指向n1 n2;//指针后移n2 n3;//指针后移if (n3)//判断n3是否为NULLn3 n3-next;//指针后移}return n1;//返回n1指针指向的位置
}思路二 头插法
如果觉得上面这种思路有点绕的话可以看看下面这种思路将原链表的结点从头到尾一个个地拿下来头插到一个新链表中这个新链表起始时为一个空链表。
这样依次进行下去最终就能得到一个“反转后的链表”。
代码实现
struct ListNode {int val;struct ListNode *next;
};struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur head;//记录当前待头插的结点struct ListNode* newhead NULL;//新链表初始时为空while (cur)//链表中结点头插完毕时停止循环{struct ListNode* next cur-next;//记录下一个待头插的结点cur-next newhead;//将结点头插至新链表newhead cur;//新链表头指针后移cur next;//指向下一个待头插的结点}return newhead;//返回反转后的头指针
}2.总结
今天我们通过两种思路分析并完成反转链表这道链表OJ题目也更加深层次了解和使用了头插法这个思路在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
