① 输入一组整型元素序列使用尾插法建立一个带有头结点的单链表。
② 实现该线性表的遍历
③ 在该单链表的第i个元素前插入一个整数。
④ 删除该单链表中的第i个元素其值通过参数将其返回。
⑤ 建立两个按值递增有序的单链表将他们合并成一个按值递减有序的单链表。要求利用原来的存储空间
线性表整表创建的思路:
对于每個链表来说他所用的空间和大小是不需要预先制定,可以动态创建即根据需要临时创建。所以创建创建链表的过程就是动态生成链表嘚过程也即是空表初始状态起,依次建立结点然后插入链表中
循环:生成新节點node将输入的数据作为node结点的指针域,将node结点插入头节点与前一个新节点之间
1.初始化空链表L,让L头节点指针指向NULL建立一个带头節点的空链表
创建一个指向表尾的指针q
循环:创建新节点p,将输入的数据作为新节点的数据域将新节点插入到表尾
在带头节点的单链表中,头指针只囿一个域,即链指针,它指向头节点,头节点有两个域,一个是数据域,值为0 (NULL),还有一个域,链指针,这个指针链指向单头指针指向链表的第一个数据节点數据元素
而在不带头节点的单链表中,头节点也只有一个链指针,但它指向单头指针指向链表的第一个数据节点数据元素
什么时候要使用带头節点的单链表?
为了在第一个数据元素前面加入新元素或者删除第一个节点时头指针的值不变,在第一个数据前面要加一个所谓的头节点
已知n个人(以编号12,3…n分别表礻)围坐在一张圆桌周围从编号为1的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数数到m的那个人又出列;依此规律重複下去,直到圆桌周围的人全部出列问最后一个出环的人的原编号。
用在单链表中删除一个结点的思想来解决此题
设一个没有头结点指針的单链表一个指针指向此单链表中间的一个结点(不是第一个,也不是最后一个结点)将该结点从单链表中删除,要求时间复杂度O(1)
首先建立一个没有头指针的环形链表,并从1到length对其初始化即为每个人的原始编号;
定义一个计数器count,若其指向待删除的前一个則将它的下一个结点删除。