c++链表合并_灯火如昼的博客-爱代码爱编程
有l1和l2两个链表,这两个链表降序排列,把l2合并到l1中,并按降序排列,同时清空l2链表。
例如l1[9,8,7,6],l2[12,11,10,5,4,3,2,1],合并后l1[12,11,10,9,8,7,6,5,4,3,2,1],l2[ ]
#include
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
//创建链表
struct ListNode* createlist()
{
struct ListNode* headNode = (struct ListNode*)malloc(sizeof(struct ListNode));
headNode->next = NULL;
return headNode;
};
//创建节点
struct ListNode* creatNode(int val)
{
struct ListNode* NewNode = (struct ListNode*)malloc(sizeof(struct ListNode));
NewNode->val = val;
NewNode->next = NULL;
return NewNode;
};
//打印链表
void printLidst(struct ListNode* headNode)
{
struct ListNode* pMove = headNode->next;
while (pMove)
{
printf(“%d\t”, pMove->val);
pMove = pMove->next;
printf(“\n”);
}
}
//插入节点、参数:插入哪个链表,插入节点数据是多少 //头插
void insertNodeByHead(struct ListNode* headNode, int val)
{
//创建插入的节点
struct ListNode* newNode = creatNode(val);
newNode->next = headNode->next;
headNode->next = newNode;
}
void MergeTwoList(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* p1 = l1;
struct ListNode* temp1;
struct ListNode* temp2;
while (l1->next != NULL || l2->next != NULL)
{
if (l1->next != NULL && l2->next != NULL)
{
if (l1->next->val < l2->next->val)
{
temp1 = l1->next;
temp2 = l2->next;
l2->next = l2->next->next;
l1->next = temp2;
l1->next->next = temp1;
l1 = l1->next;
}
else{
if (l1->next != NULL)
l1 = l1->next;
}
}
else if (l1->next != NULL )
{
l1 = l1->next;
}
else if ( l2->next != NULL)
{
temp1 = l1->next;
temp2 = l2->next;
l2->next = l2->next->next;
l1->next = temp2;
l1->next->next = temp1;
l1 = l1->next;
}
}
printLidst(p1);
cout << l2->next << endl;
cout << l1->next << endl;
}
int main()
{
//动态申请内存链表
struct ListNode* list1 = createlist();
insertNodeByHead(list1, 5);
insertNodeByHead(list1, 6);
insertNodeByHead(list1, 7);
insertNodeByHead(list1, 8);
insertNodeByHead(list1, 9);
//printLidst(list1);
struct ListNode* list2 = createlist();
insertNodeByHead(list2, 1);
insertNodeByHead(list2, 2);
insertNodeByHead(list2, 3);
insertNodeByHead(list2, 4);
insertNodeByHead(list2, 10);
insertNodeByHead(list2, 11);
insertNodeByHead(list2, 12);
//printLidst(list2);
MergeTwoList(list1, list2);
system("pause");
return 0;
}