图说线性表 - 搞懂链表从这篇文章开始，2021 必看 -Java 高级面试题总结
if(m < l.data[i])
{
return i; // 找到第一个比 m 大的元素的位置返回
}
}
return i;//如果整个顺序表都不大于 m，则返回最后的位置
}
/**
新增元素的方法
l 顺序表
m 需要新增的元素
*/
void insertElement(SqList &l,int m) // 顺序表本身需要发生变化所以传入的是引用型
{
int p,i;
p = findElement(l,m);
for(i=l.length-1;i>=p;--i) // 条件为 i>=p ,p 位置的元素也需要移动
{
l.data[i+1] = l.data[i];//从顺序表的最后开始向右移动
}
l.data[p] = m;
++(l.length);
}
顺序表的删除操作
删除操作与插入操作相反，删除掉元素后，将后续元素都前移即可。
例 2：删除顺序表 L 中下标为 p (0<=p<=l.length-1)的元素，成功返回 1，否则返回 0，并将删除的数值赋值给 e。
分析题目可知：
1 需要删除的元素位置为 p
2 删除元素前需要将值赋值给 e
需要进行的步骤如下：
1 找到需要删除的元素的位置，题目已提供 p (如果没有提供位置，需要循环查找)
2 将删除元素 p 赋值给元素 e
3 将 P 后的元素左移 (与插入不同，删除要从小下标的开始移动)
代码：
/**
删除元素的方法
l 顺序表
p 需要删除元素的位置
e 删除元素赋值的变量
*/
int deleteElement(SqList &l,int p,int &e)//需要改变的元素用引用变量
{
int i;
if( p < 0 || p > l.length -1) return 0;
e = l.data[p];
for(i=p;i < l.length-1;++i){//判断条件应为 i < l.length-1 ,如果为 i < l.length i+1 会下标越界
l.data[i] = l.data[i+1];
}
--(l.length)
return 1;
}
2.3 单链表的操作
==========
链表的相关操作是数据结构中比较常用的，这部分需要划重点。
单链表的插入操作
单链表的插入主要有尾插法、头插法两种。
尾插法比较常规就是将新加的结点依次链接到链表最后一个结点。
尾插法:
/**
C 准备要插入的链表
a 数组，要插入到链表中的元素
n 将要插入的节点数
*&C 指针型变量在函数体中需要改变的写法
顺序表 &L （ 普通变量 &m ）引用型变量需要改变的写法
*/
void createListR(ListNode *&C,int a[],int n) // 要改变的变量传引用型
{
ListNode *s,*r; // 指针 r 准备指向 C，s 准备指向要插入的节点
int i; // 循环使用的变量
C = (ListNode*) malloc (sizeof(ListNode)); //申请 C 的头结点空间
C -> next = NULL; // 申请头结点空间时一定不要忘记将头结点指针指向 NULL
r = C; //r 指向头节点
for(i=0;i<n,++i)
{
s = (ListNode*)malloc(sizeof(ListNode));//s 指向新申请的节点
s -> data = a[i]; // 值域赋值
r->next = s; // 插入新的结点
r = r->next;// 指针移动到终端结点，准备在终端插入新结点
}
r ->next = NULL;//插入完成后将 ，终端结点的指针域设置为 NULL，C 建立完成
}
头插法则是将新加的结点始终插入在头结点的后面，因此越早插入的结点在链表中的位置实际上越靠后。
图示：
头插法：
/**
C 准备要插入的链表
a 数组，要插入到链表中的元素
n 将要插入的节点数
*&C 指针型变量在函数体中需要改变的写法
顺序表 &L （ 普通变量 &m ）引用型变量需要改变的写法
*/
void createlistF(ListNode *&C,int a[],int n)
{
ListNode *s;
int i ;
C = (ListNode *)malloc( sizeof(ListNode));
C -> next = NULL;
for(i=0;i<n;++i)
{
s = (ListNode*)malloc(sizeof(ListNode));
s->data = a[i];
//头插法
s->next = C->next;//图中第二步
C->next = s;//图中第三步
}
}
单链表的删除操作
链表的删除操作就比较简单了，要删除第 m 个结点，需要找到第 m-1 个结点，将第 m-1 个结点的指针指向 m+1 个结点就可以了。
相关操作：
q = p->next;//先将要删除的结点赋值给 q
p->next = p->next->next; //第二步操作
free(q);
单链表的查找操作
例 3： 查找链表 L(带头结点) 中是否有一个值为 m 的节点，如果有则删除该节点，返回 1，否则返回 0.
/**
L 查找的链表
m 链表值域查找的值
*/
int deleteElement(ListNode *L,int m )
{
ListNode *p,*q; // 定义一个指针 p，在链表中一直往下找 , q 作为删除节点的
p = L;
while(p->next != NULL)
{
if(p->next->data == x){ // 注意此处是 p->next->data ==x,而不是 p->next == x
break;
}
p = p -> next;
}
if(p -> next == NULL)
{
return 0;
}
else
{
q = p->next; // 要删除的节点是 p->next ，q
p->next = p->next->next;
free(q);
return 1;
}
}
单链表的合并操作
链表的基本的查询 、插入、 删除操作的重点部分已经回顾完了，下面来看看 leetCode 的例题---合并链表:
leetcode 21
题目如下：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
思路：
1 升序的两个链表，合并成一个升序新链表
2 创建头指针，使用尾插法循环比较 两个链表的值，把值小的插入到头结点后，移动指针
3 如果循环结束后某一个链表指针没有移动到末尾，将新链表末尾指向这个指针的结点
图解：
题解：
常规解法：
/**
Definition for singly-linked list.
struct ListNode {
uct ListNode *next;
};
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode head = (struct ListNode)malloc(sizeof(struct ListNode));//申请头结点空间
struct ListNode *r = head;//定义移动指针 r ，r 始终指向终端结点
while( l1 !=NULL && l2 != NULL){
if(l1 -> val <= l2 -> val){
r -> next = l1;//将 r->next 指向 l1
l1 = l1->next; //l1 指针前移
r = r->next; //r 指针前移
}else{
r -> next = l2;
l2=l2 -> next;
r = r-> next;
}
}
r->next = NULL;
if(l1 != NULL){ // 如果循环插入结束后仍有剩余结点，直接插入到末尾
r -> next = l1;
}
if(l2 != NULL){// 如果循环插入结束后仍有剩余结点，直接插入到末尾
r -> next = l2;
}
return head ->next;//不用返回头结点
}
上面的解法结果没什么问题，就是我们新创建了一个头结点，如果置之不理的话，可能会导致内存泄漏。
下面是不创建头结点的解法，只是在开始的时候巧妙地使用两个链表中最小表头为新链表的头结点，后面操作类似
不申请头结点解法：
/**
Definition for singly-linked list.
struct ListNode {
};
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
struct ListNode *head;//定义头指针
if (l1->val < l2->val){
head = l1; //如果 l1 表头元素值较小 ，将头指针指向 l1
l1 = l1->next;// l1 指针右移
}else{
head = l2; //如果 l2 表头元素值较小 ，将头指针指向 l1
l2 = l2->next;//l2 指针右移
}
struct ListNode *r = head;
// l1,l2 一直向后遍历元素，向 head 中按序插入，直至 l1 或 l2 为 NULL
while(l1 && l2){
if(l1->val < l2->val){
r->next = l1;
l1 = l1->next;
r = r->next;
}else{
r->next = l2;
l2 = l2->next;
r = r->next;
}
}
// l1 或 l2 为 NULL,此时将不会空的链表接到最后即可
r->next = l1 ? l1 : l2;
return head;
}
以上不同的解法都是使用了链表的尾插法，因为尾插法正好符合题目的要求，新插入的结点也是依次递增的。
如果题目要求变成要求 将两个升序链表合并为一个新的?降序?链表并返回，这时使用头插法就比较合适了。
合并为一个新的 降序 链表,头插法：
/**
Definition for singly-linked list.
struct ListNode {
};
*/
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论