C++ 结构体指针链表基本操作
作者:
滑稽_ωノ
,
2021-10-19 00:38:12
,
所有人可见
,
阅读 765
#include<cstdio>
#include<cstring>
struct Node {
int val;
Node* next;
};
// 尾插
void add(Node* &head, Node* &fail, int val)
{
Node* p = new Node();
p->val = val;
p->next = NULL;
if (head == NULL)
{
head = fail = p;
}
else
{
fail->next = p;
fail = p;
}
}
void print(Node* head)
{
for(Node *p = head; p != NULL; p = p->next) printf("%d ", p->val); puts("");
}
// 归并两个有序链表返回头节点
Node* merge(Node* headA, Node* headB)
{
if(headA == NULL) return headB;
if(headB == NULL) return headA;
Node *p1 = headA, *p2 = headB, *resHead = headA;
if(p2->val < p1->val)
{
resHead = p2;
p2 = p2->next;
}
else
{
p1 = p1->next;
}
Node *p = resHead;
while(p1 != NULL and p2 != NULL)
{
if(p1->val <= p2->val)
{
p->next = p1;
p1 = p1->next;
}
else
{
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if(p1 != NULL) p->next = p1;
if(p2 != NULL) p->next = p2;
return resHead;
}
int main()
{
Node *headA = NULL, *failA = NULL;
Node *headB = NULL, *failB = NULL;
int n, a[10];
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
add(headA, failA, a[i]);
}
print(headA);
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
add(headB, failB, a[i]);
}
print(headB);
Node* list = merge(headA, headB);
print(list);
return 0;
}
输入数据
3
1 3 5
4
2 4 6 8
输出数据
1 3 5
2 4 6 8
1 2 3 4 5 6 8