3.6 章节练习
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 3.6 章节练习
## 3.6.1 习题
【习题3-1】（13分）已知两个长度分别为m和n带头结点的升序链表L1和L2，若将它们合并为一个长度为m+n的升序链表。请设计一个时间和空间上尽可能高效的算法，返回合并后的结点的结构定义如下：
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;
原资料配图 · 转写内容请回源核验
类型定义(2)采用C或C++语言描述算法，关键之处给出注释。
间复杂度。
(1)写出链表结点的数据
(3) 说明所设计算法的时
<!-- page 120 -->
【习题3-5】（13分）设有两个从小到大排序（无重复元素）的带头结点的有序链表L1和L2。设计一个空间复杂度为O(1)且时间上尽可能高效的算法，求这两个链表交运算的算法(即
typedef struct node{
int data;
struct node *next;
}node, *LinkList;
原资料配图 · 转写内容请回源核验
str1和str2 分别指向两个单词所在单链表的头结点，链表结点结构为：
<table><tr><td>data</td><td>考 next</td><td></td><td>机</td></tr></table>
请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p)。要求：1）给出算法的基本设计思想。2）根据设计思想，采用C 或C++或Java语言描述算法，关键之处给出注释。3) 说明你所设计算法的时间复杂度。
<!-- page 123 -->
【2015 年 41 题】(15 分)用单链表保存 m 个整数，结点的结构为 [data，link]，且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表HEAD 如下： 成村
原资料配图 · 转写内容请回源核验
(1)给出算法的基本设计思想。(2)使用C 或C++语言，给出单链表结点的数据类型定义。(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。(4)说明你所设计算法的时间复杂度和空间复杂度。
<!-- page 124 -->
【2019年41题】（13分)设线性表采用带头结点的单链表保存，链表中的结点定义如下：
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; // L2跳过头结点
while (p!=NULL){
ListNode* temp=p->next; // temp暂存下一个结点
Find_Insert(L1, p);
p=temp;
}
return L1;
}
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)
p->next=L1;
else
return L3; p->next=L2;
}
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; //将p插入到pre之后
}
ListNode* ans(ListNode *L1,ListNode *L2)
{
ListNode* p=L2->next; // L2跳过头结点
while (p!=NULL)
{
ListNode* temp=p->next;
Find_Insert(L1, p);
p=temp;
p=L1->next;
int len=0;
int a[max_nm];
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;
}
}
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是新链表的起点
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;
}
typedef struct node{
int data;
struct node *next;
}node, *linklist;
int IsPalindrome(linklist L)
{
if (L==NULL I|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;
}
}