学长冷月带你怒刷LeetCode之反转链表

作者: 学长冷月 分类: LeetCode算法笔记 发布时间: 2020-05-06 点击量: 456

前言

链表的操作是数据结构中最基础的算法之一,反转列表也是一道经典的笔试题。很多公司的面试题库中都有这道题,有的公司明确题目要求不能使用额外的节点存储空间,有的没有明确说明,但是如果面试者使用了额外的节点存储空间做中转,会得到一个比较低的分数。本题选自leetcode的206题,感兴趣的小伙伴可以去练习一下。206.反转链表

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

冷月题解

因为是操作单链表,而单链表是单向指向的,如果要求空间复杂度为O(1)的情况下,我们只能使用迭代是方式。需要新增加两个指针。冷月把完整实例代码放在博客上了,大家可以进入查看学长冷月带你怒刷LeetCode之反转链表

struct ListNode * cur = head; //指向当前节点

struct ListNode * pre = NULL; //指向上一个节点

一开始,我们链表是如下的形式:
反转链表

此时head不为空,我们进入第一次循环。
head = head -> next; //指向下一个结点

cur->next = pre; //当前节点 指向 上一个节点
如下图所示:反转链表

这时,我们已经将第一个节点指向了pre,也就是说将第一个节点反转了过来,下一步我们要将pre和cur移动一下位置,方便下一次循环。

pre = cur; //指针域往后挪动

cur = head; //指针域往后挪动
如下图所示:
反转链表
这时已经完成了第一次循环的所有步骤,我们成功将第一个节点反转,并且从第二个节点开始成为了新的表头,大家可以与第一张图片对比一下,是不是很相似呢?然后进入第二次循环,循环的步骤方法和第一次的一模一样,第二次循环完后的图示如下:
反转链表

再经过四次循环后,cur = head = NULL,将会跳出循环,我们只需要将pre 返回出去即可,获得反转后的链表。图示如下:
反转链表

完整代码如下:

  1. /**
  2. 公众号:学长冷月
  3. **/
  4. struct ListNode* reverseList(struct ListNode* head){
  5. struct ListNode * cur = head; //指向当前节点
  6. struct ListNode * pre = NULL; //指向上一个节点
  7. while(head){ //如果链表不为空则进入循环
  8. head = head -> next; //指向下一个结点
  9. cur->next = pre; //当前节点 指向 上一个节点
  10. pre = cur; //指针域往后挪动
  11. cur = head; //指针域往后挪动
  12. }
  13. return pre;
  14. }

总结一下

这道反转链表的题属于很基础的入门题,是每位小伙伴都应该掌握的难度。光说不练假把式,大家要先理解,然后将代码自己实现一下才能将知识转变成自己的。冷月会在博客上首发《怒刷LeetCode》系列文章,感兴趣的小伙伴可以给冷月的博客加一个收藏冷月的博客,方便获取最新的推送~

如果觉得我的文章对您有用,可以关注冷月的公众号或者加冷月的微信。获得独家整理的学习资源和日常干货推送!

学长冷月的公众号

学长冷月的公众号

学长冷月的微信

学长冷月的微信
LeetCode,链表,学长冷月
0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注