常见数据结构-链表
【摘要】 针对链表的插入、删除操作,需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。head = null 表示链表中没有节点,head 表示头节点,指向链表中的第一个节点。
一,单链表结构定义
C/C++ 数组:一组具有相同类型数据的集合。结构体:不同类型数据的集合。
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
二,写链表代码的技巧
2.1,技巧一:理解指针或引用的含义
指针:指针存放某个对象地址。将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针。
2.2,警惕指针丢失和内存泄露
- 插入节点时,一定要注意操作是顺序;
- 删除链表时,也一定要记住手动释放内存空间。
2.3,利用哨兵简化实现难度
针对链表的插入、删除操作,需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。head = null
表示链表中没有节点,head
表示头节点,指向链表中的第一个节点。
引入哨兵节点,哨兵节点不管链表是否空,head
指针都会已知指向哨兵节点。有哨兵节点的链表叫作带头链表,反之则是不带头链表。
利用哨兵简化编程难度的技巧再插入排序、归并排序、动态规划等代码中都有用到。
2.4,重点留意边界处理条件
写链表代码一定要检查以下情况下,代码逻辑能否正常工作。
- 链表为空;
- 链表只有一个节点;
- 代码处理头节点和尾节点
2.5,举例画图,辅助思考
处了举例画图辅助我们思考问题之外,剩下最关键的就是多写多练、熟能生巧。 5
个常见链表操作如下:
- 单链表反转
- 链表中环的检测
- 两个有序链表的合并
- 删除链表倒数第
n
个节点 - 求链表的中间节点
参考资料
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)