题目
给定一个有序的循环链表,在其中插入一个值,保持该循环链表依然有序。
分析
首先看下循环链表的结构,如下图所示为一个循环链表,其尾结点指向头结点,从而形成一个循环。给定的链表结点可以是链表任意一个结点,这个结点不一定是链表头结点,从而这也增加了该题的难度。
此时若是要在链表中插入4,则插入后的链表如下所示:
可以看到插入4后,链表依然有序。
在解决这个问题前,先来看一个简化的问题,就是在一个有序单链表中插入结点,仍然保证其有序。这个问题的代码相信多数人都很熟悉,一般都是分两种情况考虑:
1)如果原来链表为空或者插入的结点值最小,则直接插入该结点并设置为头结点。
2)如果原来链表非空,则找到第一个大于该结点值的结点,并插入到该结点的前面。如果插入的结点值最大,则插入在尾部。
代码如下:
//链表结点定义
struct node {
int data;
struct node *next;
};
typedef struct node Node;
void sortedInsert3(struct node** headRef, struct node* nd)
{
if (*headRef==NULL || (*headRef)->data>=nd->data) { //情况1
nd->next = *headRef;
*headRef = nd;
} else { //情况2
struct node* current = *headRef;
while (current->next != NULL && current->next->data < nd->data)
current = current->next;
nd->next = current->next;
current->next = nd;
}
}
当然也可以把情况1和情况2放到一起考虑,代码会更简洁,如下所示:
void sortedInsert2(struct node** headRef, struct node* nd)
{
struct node** current = headRef;
while ( (*current)!=NULL && ((*current)->data<nd->data) ) {
current = &((*current)->next);
}
nd->next = *current;
*current = nd;
}
上面代码很简洁,注意它是怎么处理特殊情况的。
1)当链表为空或者插入的结点值最小时,则直接跳出循环,设置nd->next=NULL, *headRef=nd.
2)其他情况,则current为待插入结点的位置,直接将其插入即可。包括插入到尾部或者任意常规的位置。
解决方案
解决了一个轻量级的问题之后再来看原题,该题目与上面不同的地方在于它是一个循环链表,那么情况会有所不同,设待插入的结点值为x,则至少需要考虑下面三种情况:
1.prev->val ≤ x ≤ current->val:
插入到prev和current之间。
2. x是链表中最小或者最大的值:
插入x到链表头部的前面。
3.回到起始点:
插入到起始点前面。
第1和2种情况还比较容易考虑到,但是第3种情况往往会被忽略,先给出代码,再根据代码来分析这些情况为什么都需要考虑到。
void insert(Node *& aNode, int x) {
//链表为空,创建节点返回
if (!aNode) {
aNode = new Node(x);
aNode->next = aNode;
return;
}
Node *p = aNode;
Node *prev = NULL;
do {
prev = p;
p = p->next;
if (x <= p->data && x >= prev->data) break; // 情况1,找到正常位置返回,如例子中插入4到链表中
if ((prev->data > p->data) && (x < p->data || x > prev->data)) break; // 情况2,x最小或者最大,插入到链表最前面
} while (p != aNode); // 情况3,回到起始结点,停止.
Node *newNode = newNode(x);
newNode->next = p;
prev->next = newNode;
}
1)链表只有一个结点
如果x等于该结点值,则直接在情况1处理。否则情况3处理。
2)链表包含重复值
如果链表为1-*1-1,起始结点为第二个1,则在其中插入2时,由情况3处理,即最终插入到初始结点前面。会变成1-2-1-1.循环链表从第二个1开始,照样是有序的。
分享到:
相关推荐
(1)建两个带头结点的循环单链表LA,LB单循环链表, (2)将两个循环单链表合并为一个循环单链表,其头指针为LA。 六)单链表应用 建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域...
1.算法设计与分析题:将直接插入排序的内循环改造为使用对分查找实现元素插入,请写出基于对分查找的插入排序算法并给出其时间复杂度分析。 2.算法设计:将教案给出的非递归直接插入排序和冒泡排序算法用递归算法...
(4)设A与B分别为两个带有头结点的有序循环链表(所谓有序是指链接点按数据域值大小链接,本题不妨设按数据域值从小到大排列),list1和list2分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为...
内容:1、假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向某个结点的指针,试编写算法删除结点*s的直接前驱结点。 2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和其它...
假设在长度大于1的单循环链表中,既无头结点也无头指针。s 为指向某个结点的指针,试编写算法删除结点*s 的直接前驱结点。 2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和其它字符),设计...
2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点,要使操作时间最少,下列选项中,应选择的存储结构是(C) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D....
问题:实现单链表、循环链表、双向链表,支持增删操作 问题:实现单链表反转 问题:实现两个有序的链表合并为一个有序链表 问题:实现求链表的中间结点 栈 问题:用数组实现一个顺序栈 问题:用链表实现一个...
leetcode 跳跃 leetcoe 力扣刷题记录 括号匹配 合并两个有序链表 合并二叉树 翻转二叉树 x的平方根 跳跃游戏II ...从链表中删去总和值为零的连续节点 提莫攻击 最小覆盖子串
将数据插入到一个有序的序列中 做法 外层for循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据) 内层while循环加上角标>0的条件查找出要插入的何时位置 退出内层while...
## 链表* 实现单链表、循环链表、双向链表,支持增删操作* 实现单链表反转* 实现两个有序的链表合并为一个有序链表* 实现求链表的中间结点 ## 栈* 用数组实现一个顺序栈* 用链表实现一个链式栈* 编程模拟实现一个...
1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表线性表的基本功能:1、 构造:使用头插法、尾插法两种方法2、 插入:要求建立的链表按照关键字从小到大有序(静态链表不要求该项)3...
带头结点的单链表L,其中有n 个元素非递减有序排列,将元素X插入到链表中合适的位置。 提示:先创建链表,其中的元素值可由随机函数按阶段生成或键盘输入,先打印初始链表数据,然后插入新结点,再打印结果链表。 ...
5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表。 6、利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。 7、利用算法5建立两个非递减有序...
试写出一个算法,将该线性单链表分解成两个线性单链表,其中一个链表中的结点值均为奇数,而另一个链表中的结点值均为偶数,且这两个链表均按值从小到大链接。 8. 已知二叉树的后序遍历和中序遍历序列,构造对应的...
带头结点的双循环链表 4.在按值有序的线性表(5,8,11,12,1 5,20,32,41,57)中采用折半查找法查找20需要进行 次元素间的比较。 ( ) A.3 B.4 C.5 D.6 5.假定为一个顺序存储的循环队列分配的最大空间为...
4、在非空双向循环链表中,在结点q的前面插入结点p的过程如下: p->prior=q->prior; q->prior->next=p; p->next=q; ______________________; 5、已知L是无表头结点的单链表,是从下列提供的答案中选择合适的语句...
三:内容:1、假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向某个结点的指针,试编写算法删除结点*s的直接前驱结点。 2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和...
按照动态单链表结构实现如下算法(各算 法边界条件适当给出): 1)按照后插法(带头结点)、前插法 (不带头结点)、创建任意有序单循环链表(即链表的元素随机在键盘上输入),长度 限定在15之内; 2)打印(遍历...
17. 在有 n个选手参加的单循环赛中,总共将进行______场比赛。【合肥工业大学 1999三、8(2分)】 四、应用题 1. 数据结构是一门研究什么内容的学科?【燕山大学 1999 二、1 (4分)】 2. 数据元素之间的关系在...
用一种算法在一个循环的链接表里插入一个节点,但不得穿越链接表。 10.给两个变量,如何找出一个带环单链表中是什么地方出现环的? 11.哈希表和数组的定义,区别,优缺点。 12.链接表和数组之间的区别是...