3.6 章节练习
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 3.6 章节练习
## 3.6.1 习题
## 【习题3-1】
(13分）已知两个长度分别为m和n带头结点的升序链表L1和L2，若将它们合并为一个长度为m+n的升序链表。请设计一个时间和空间上尽可能高效的算法，返回合并后的带头结点的升序序链表，其头结点为L3。结点的结构定义如下：
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
typedef struct node{
int data;
struct node *next;
}node, *linklist;
原资料配图 · 转写内容请回源核验
原资料配图 · 转写内容请回源核验
## 【习题3-4】
（13分）一元稀疏多项式用带头结点的单链表L1、L2按指数降序排列（其中L1的最高次项系数>=L2的最高次项指数），请设计一个时间上尽可能高效的算法，将这两个多项式相加，结果仍按降序保存在链表中（多项式为0的时候只有头结点），返回头指针L1。结点结构（data表示系数，exp表示指数，next指向下一个结点）：
<table><tr><td>exp</td><td>data</td><td>next</td></tr></table>
例：多项式f1(x) = 3x4 + 2x3 + 1， f2(x) = 3x4 − 2x2 + 2, 结果
f3(x) = f1(x) + f2(x) = 2x3 − x2 + 3, 链表结构如下:
原资料配图 · 转写内容请回源核验
(1)写出链表结点的数据类型定义
(2)采用C或C++语言描述算法，关键之处给出注释。
(3)说明所设计算法的时间复杂度。
## 【习题3-5】
(13分）设有两个从小到大排序（无重复元素）的带头结点的有序链表L1和L2。设计一个空间复杂度为O(1)且时间上尽可能高效的算法，求这两个链表交运算的算法(即L1∩L2)。要求结果链表仍是从小到大排序，但无重复元素。
typedef struct node{
int data;
struct node *next;
}node, *LinkList;
原资料配图 · 转写内容请回源核验
设 str1和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为：
<table><tr><td>data</td><td>next</td></tr></table>
请设计一个时间上尽可能高效的算法，找出由str1 和 str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度。
## 【2015年41题】
(15 分）用单链表保存m 个整数，结点的结构为「data，link]，且Idatal≤n(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表HEAD如下：
原资料配图 · 转写内容请回源核验
则删除结点后的 HEAD为
原资料配图 · 转写内容请回源核验
要求:
(1)给出算法的基本设计思想。
(2)使用C或C++语言，给出单链表结点的数据类型定义。
(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(4)说明你所设计算法的时间复杂度和空间复杂度。
## 【2019年41题】
（13分）设线性表采用带头结点的单链表保存，链表中的结点定义如下：
<!-- page 86 -->
typedef struct node {
int data;
struct node* next;
}NODE;
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 查找并插入p
void Find_Insert(ListNode *pre, ListNode *p)
{
while (pre->next!=NULL && pre->next->val<p->val) //查找插入位置
pre=pre->next;
p->next=pre->next;
pre->next=p;
ListNode* ans(ListNode *L1, ListNode *L2)
{
ListNode* p=L2->next;
while (p!=NULL){
ListNode* temp=p->next;
Find_Insert(L1, p);
p=temp;
}
return L1;
}
}
(3) // 时间复杂度：O(mn) 空间复杂度：O(1)
ListNode* ans(ListNode *L1, ListNode *L2)
{
ListNode* L3=(ListNode*)malloc(sizeof(ListNode)); // L3作为新链表的起点
L3->next=NULL;
L1=L1->next; // L1跳过头结点
L2=L2->next; // L2跳过头结点
ListNode* p=L3;
while (L1!=NULL && L2!=NULL){
if (L1->val<=L2->val){
p->next=L1;
L1=L1->next;
}
else{
p->next=L2;
L2=L2->next;
}
p=p->next;
}
/*将链表剩余部分直接链接到新链表L3的尾部*/
if (L1!=NULL)
om
p->next=L1;
else
p->next=L2;
return L3;
}
(3) // 时间复杂度: O(m + n) 空间复杂度：O(1)
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 查找并插入p
void Find_Insert(ListNode *pre, ListNode *p)
{
pre=pre->next;
p->next=pre->next;
pre->next=p; //将p插入到pre之后
}
ListNode* ans(ListNode *L1, ListNode *L2)
{
ListNode* p=L2->next; // L2跳过头结点
while (p!=NULL)
{
ListNode* temp=p->next; // temp暂存下一个结点
Find_Insert(L1, p);
p=temp;
道汁
p=L1->next;
int len=0;
int a[max_nm]; // max_nm是m+n之和的最大值
while (p!=NULL)
{
a[len]=p->val;
len++;
p=p->next;
}
p=L1->next;
for (int i=len-1;i>=0;i--)
{
p->val=a[i];
p=p->next;
}
return L1;
}
}
(3) // 时间复杂度：O((m + n)²) 空间复杂度: O(m + n)
ListNode* Head_Insert(ListNode* L, ListNode* p)
{
ListNode* temp=p->next;
p->next=L->next;
L->next=p;
return temp;
}
ListNode* Merge(ListNode *L1, ListNode *L2)
{
ListNode* L3=(ListNode*)malloc(sizeof(ListNode));
L3->next=NULL;
L1=L1->next; // L1跳过头结点
L2=L2->next; // L2跳过头结点
while (L1!=NULL && L2!=NULL)
if (L1->val<=L2->val)
L1=Head_Insert(L3, L1);
else
L2=Head_Insert(L3, L2);
//将链表剩余结点依次头插法插入新链表L3中
while (L1!=NULL)
L1=Head_Insert(L3, L1);
while (L2!=NULL)
L2=Head_Insert(L3, L2);
return L3;
}
(3) // 时间复杂度: O(m + n) 空间复杂度：O(1)
typedef struct node{
int data;
struct node *next;
}node, *linklist;
int IsPalindrome(linklist L)
{
if (L==NULL || L->next==NULL)
return 1;
linklist p=L->next;
int len=0;
while (p!=NULL)
{
len++;
p=p->next;
}
linklist left=L, right;
for (int i=1;i<=len/2;i++)
{
left=left->next;
right=L;
for (int j=1;j<=len-i;j++)
right=right->next;
if (left->data!=right->data)
return 0;
}
return 1;
}