专栏首页C语言入门到精通数据结构 | 每日一练(44)

数据结构 | 每日一练(44)

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1.知 L1、L2 分别为两循环单链表的头结点指针,m,n 分别为 L1、L2 表中数据结点个数。要求设计一算法,用最快速度将两表合并成一个带头结点的循环单链表。

类似本题的另外叙述有:

(1)试用类 Pascal 语言编写过程 PROC join(VAR la:link; lb:link) 实现连接线性表 la 和

lb(lb 在后)的算法,要求其时间复杂度为 0(1), 占用辅助空间尽量小。描述所用结构。

(2)设有两个链表,ha 为单向链表,hb 为单向循环链表。编写算法,将两个链表合并成一个单向链表,要求算法所需时间与链表长度无关。

正确答案

ps:||代表注释

1.[题目分析]循环单链表L1和L2数据结点个数分别为m和n ,将二者合成一个循环单链表时,需要将一个循环链表的结点(从第一元素结点到最后一个结点)插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“,因此应找结点个数少的链表查其尾结点。

LinkedList Union(LinkedList L1,L2; int m,n)∥L1和L2分别是两循环单链表的头结点的指针,m和n分别是L1和L2的长度。

∥本算法用最快速度将L1和L2合并成一个循环单链表。

{ if(m<0||n<0) {printf(“表长输入错误\n”);exit(0);}

if(m<n) ∥若m<n,则查L1循环单链表的最后一个结点。

{ if(m==0) return(L2);∥L1为空表。

else{p=L1;

while(p->next!=L1) p=p->next;∥查最后一个元素结点。

p->next=L2->next;∥将L1循环单链表的元素结点插入到L2的第一元素结点前。

L2->next=L1->next;

free(L1);∥释放无用头结点。

}

}∥处理完m<n情况

else∥ 下面处理L2长度小于等于L1的情况

{ if(n==0) return(L1);∥L2为空表。

else{p=L2;

while(p->next!=L2) p=p->next;∥查最后元素结点。

p->next=L1->next;∥将L2的元素结点插入到L1循环单链表的第一元素结点前。

L1->next=L2->next;

free(L2);∥释放无用头结点。

}

}∥算法结束。

类似本题叙述的其它题解答如下:

(1)[题目分析]本题将线性表la和lb连接,要求时间复杂度为O(1),且占用辅助空间尽量小。应该使用只设尾指针的单循环链表。

LinkedList Union(LinkedList la,lb)

∥la和lb是两个无头结点的循环单链表的尾指针,本算法将lb接在la后,成为一个单循环链表。

{ q=la->next; ∥q指向la的第一个元素结点。

la->next=lb->next; ∥将lb的最后元素结点接到lb的第一元素。

lb->next=q; ∥将lb指向la的第一元素结点,实现了lb接在la后。

return(lb); ∥返回结果单循环链表的尾指针lb。

}∥算法结束。

[算法讨论]若循环单链表带有头结点,则相应算法片段如下:

q=lb->next; ∥q指向lb的头结点;

lb->next=la->next; ∥lb的后继结点为la的头结点。

la->next=q->next; ∥la的后继结点为lb的第一元素结点。

free(q); ∥释放lb的头结点

return(lb); ∥返回结果单循环链表的尾指针lb。

(2)[题目分析]本题要求将单向链表ha和单向循环链表hb合并成一个单向链表,要求算法所需时间与链表长度无关,只有使用带尾指针的循环单链表,这样最容易找到链表的首、尾结点,将该结点序列插入到单向链表第一元素之前即可。其核心算法片段如下(设两链表均有头结点)

q=hb->next; ∥单向循环链表的表头指针

hb->next=ha->next; ∥将循环单链表最后元素结点接在ha第一元素前。

ha->next=q->next; ∥将指向原单链表第一元素的指针指向循环单链表第一结点

free(q); ∥释放循环链表头结点。

若两链表均不带头结点,则算法片段如下:

q=hb->next; ∥q指向hb首元结点。

hb->next=ha; ∥hb尾结点的后继是ha第一元素结点。

ha=q; ∥头指针指向hb的首元结点。

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

-end-

本文分享自微信公众号 - C语言入门到精通(gh_780327809188)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 | 每日一练(73)

    ——老子

    C语言入门到精通
  • 数据结构 | 每日一练(48)

    1.设 Listhead 为一单链表的头指针,单链表的每个结点由一个整数域 DATA 和指针域 NEXT 组成,整数在单链表中是无序的。编一 PASCAL 过程...

    C语言入门到精通
  • 数据结构 | 每日一练(58)

    ——老子

    C语言入门到精通
  • 数据结构 | 每日一练(73)

    ——老子

    C语言入门到精通
  • 剑指offer代码分析——面试题13在O(1)内删除链表结点

    本题详细解析都已在代码中注释了: /** * 给一个单链表,头指针为first,请用O(1)时间删除其中节点p * @author chibozhou *...

    大闲人柴毛毛
  • [leetcode链表系列] 1 链表的中间节点

    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NU...

    我是程序员小贱
  • 数据结构 | 每日一练(21)

    ——老子

    C语言入门到精通
  • 每天一道剑指offer-删除链表中重复的结点

    在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1...

    乔戈里
  • [LeetCode Python 3] 876. Middle of the Linked List(链表的中间结点)

    设置两个指向头节点的快慢指针,快指针每次走两步,慢指针每次走一步,当快指针到达最后结点或为空时,慢指针指向的就是中间结点 。

    Woodson
  • 数据结构 第4-2讲 双向链表

    链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?

    rainchxy

扫码关注云+社区

领取腾讯云代金券