链表问题首先要注意的,必须要注意的是题意:是否为空链表,是否有环,是否是单链表
链表节点的定义如下:
typedef struct list {
int key;
struct list *next;
}list;
已知链表的头结点head,写一个函数把这个链表逆序
关键点:1、是否是空链表;2、是否是循环链表,如果是完全循环链表(整个链表就是一个环),则直接逆序就行,如果不是却还有环,则没法逆序……
以下代码为未处理环的链表逆序
list * reverse(list * head) {
list * h = head;
list * new_head = NULL, *temp;
if (h==NULL) return h;//如果是空链表
do{
temp = h;
h = h -> next;
temp -> next = new_head;
new_head = temp;
} while(h != NULL && h != head) //检测是循环链表
return new_head;
}
已知两个链表head1 和head2 各自有序,请把它们合并成一个链表依然有序。(保留所有结点,即便大小相同)
关键点:各自有序是都是从大到小,即是否相同规格,如果不一样,则需要先将其中一个逆序
用递归方法进行的代码如下:
list * merge (list *list1_head, list *list2_head){
list * res;
if(list1_head == NULL) return list2_head;
if(list2_head == NULL) return list1_head;
if(list1_head->key > list2_head->key) {
res = list1_head;
res->next = merge(list1_head->next, list2_head);
} else {
res = list2_head;
res->next = merge(list1_head,list2_head->next);
}
return res;
}
写一个程序,计算链表的长度
unsigned int list_len(list *head){
unsigned int len = 0;
list * h = head;
if(h == NULL)return 0;
do {
len++;
h = h->next;
} while (h != NULL && h != head)
return len;
}
一个单向链表的头指针,可能循环链表(不是NULL结束),问怎么找出这个链表循环部分的第一个节点。
使用两个指针,一个为p1步长为1,另一个为p2步长为2,如果p2可以追上p1,则说明有环;
然后让p2固定,p1再来一圈,再与p2相遇时就能求出环的长度L;
然后令p1和p2都步长为1,从链表的头开始走,让他们间距为L,则第一个相等的地方,就是环的起点。
找出单向链表中的中间结点
利用步长为1,步长为2指针,当步长为2的指针到达末尾时,步长为1的指针就刚好达到中间(链表长度的奇偶性,注意处理边界)
给定单链表中的一个结点指针,在O(1)时间删除该结点。
将该节点的下一个节点的值copy到这个节点,然后删除下一个节点,注意如果要删除的是尾指针,即当前节点没有下一个节点(指向NULL),则直接置空
给定单链表中的一个结点指针p(非空),在p前面插入一个结点。
办法与前者类似,首先分配一个结点q,将q插入在p后,接下来将p中的数据copy入q中,然后再将要插入的数据记录在p中。
查找链表中倒数第k个结点
设置步长相同,间距为k的指针,其特点在当内存无法存放所有元素,需要从硬盘读取时,性能卓越,k在可以接受的情况下可以一次读取到内存,大大提高了效率。
注意考虑边界情况:如果链表的长度不足k,它就不存在k个元素,因此必须在两个指针的出发阶段检查最先出发的当前指针是否已经到了链表尾。
判断两个链表是否相交
只有一个链表有环的情况下是不会相交的,只有都有环或者都没有环的情况下才可能相交;
都没有环的情况下最简便的方法就是判断链尾是否相交即可;
都有环的情况下,分别找到环上的任一点,一个不动,另一个步进,即可判断是否相交
两个单向链表,开头结点不一样,在中间某处开始,结点一样了,找出它们的第一个公共结点。
可以通过判断最后一个节点是否相同,判断是否相交。如果相交,可以统计两个链表的长度,设一个为a,一个为b,然后这样再搞两个指针,一个先走|a-b|步,另一个再走,当它们相等时就是第一个公共结点。
链表排序
最好使用归并排序算法。堆排序、快速排序这些在数组排序时性能非常好的算法,在链表只能“顺序访问”的魔咒下无法施展能力,但是归并排序却如鱼得水,非但保持了它O(nlogn)的时间复杂度,而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)
分享到:
相关推荐
链表总结,c语言版本,巩固基础知识,适用于求职面试,来自互联网,版权归著者
链表问题总结 是一个电子文档 打开就可以用 格式.doc
java 链表心得,对于感到困难的朋友会有很大帮助,与其他语言互通
做有关链表的编程时,这个很实用! 不信试试! 我个人是觉得在做有关链表的程序时,是很好用的
C语言中关于链表的总结内容,内附代码例题,详细的有条理的讲解链表内容
链表是最基本的数据结构,凡是学计算机的必须的掌握的,在面试的时候经常被问到,关于链表的实现,百度一下就知道了。 在此总结一下与链表相关的练习题。题目很全,好好消化。
c语言中链表的学习,总结相当到位,对于初学者有很大的帮助!
C语言结构体链表的排序方法汇总 ========================== 功能:选择排序(由小到大) 返回:指向链表表头的指针 ========================== */ /* 选择排序的基本思想就是反复从还未排好序的那些节点中, ...
数据结构,链表所有综合面试题型汇总,有大神漏缺的给我留言
链表是学习数据结构的大门,在微软等大公司招聘c\c++技术人员的时候有3个会必然出现 的东西,指针、链表、二叉树!
城市链表课程设计里面含有详细文档,以及实现代码,资源完整。
数组和链表总结 数组和链表.txt
1. 剑指offer 22.返回倒数第k个节点:林伟龙 【20:15-20:34】法思路1. 遍历第次链表计算链表度2. 遍历第次链表找到 第 k 个 元素法
数据结构第六章课件及建立二叉树的二叉链表存储结构汇总,
数组和链表的对比分析 数组和链表.docx
php数组当链表-php数组和链表的区别总结 数组和链表.pdf
顺序存储和链式存储 1 数组—顺序存储 1 链表—链式存储 2 链表概述 3 单链表 4 单链表概念和简单的设计 4 链表的初始化 5 头插入法创建单链表 6 尾插入法创建单链表 7 遍历单链表如打印、修改 8 ...关于链表的总结 23
面试题总结:数组和链表的区别 数组和链表.pdf
php数组和链表的区别总结 数组和链表.pdf
数据结构的实验报告2链表的基本操作运算 实验内容 编写程序实现链表的建立和基本运算,并完成以下功能: 1、初始化链表、建立新链表。 2、查找节点。 3、 删除节点。 4、 插入节点。 5、 获得链表长度。 6、 退出。