C++
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define error 1
#define ok 0
typedef int status;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}
LNode, *LinkList;
status InitList( LinkList &L){
L = ( LNode *)malloc(sizeof(LNode));
if(L == NULL)
{
return error;
}
printf("initlist");
L-> next = NULL;
return ok;
}
status InsertList( LinkList &L, int i, ElemType e){
LNode *p = L;
int j = 0;
while(p && j<i-1){
p = p->next;
++j;
}
if(!p || j>i-1){
return error;
}
LNode *q;
q = (LNode *)malloc(sizeof(LNode));
q->data = e;
q-> next = p->next;
p-> next = q;
return ok;
}
status DeleteList(LinkList &L, int i, ElemType &e){
LNode *p = L;
int j = 0;
while(p->next && j<i-1){
p = p->next;
++j;
}
if(!(p->next) || j>i-1)
{
return error;
}
LNode *q;
q = (LNode *)malloc(sizeof(LNode));
q = p->next;
e = q->data;
p->next = q->next;
free(q);
return ok;
}
status CreatList(LinkList &L, int n){
L = (LinkList)malloc(sizeof(LNode));
if(L==NULL)
{
return error;
}
L->next = NULL;
int i ;
for(i=n; i>0; i--){
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s==NULL)
{
return error;
}
scanf("%d",&s->data);
s->next = L->next;
L->next = s;
}
return ok;
}
status MergeList(LinkList &L1, LinkList &L2, LinkList &L3){
LNode *a = L1->next;
LNode *b =L2->next;
LNode *c ;
L3 = c = L1;
while(a && b)
{
if(a->data <= b->data)
{
c ->next = a;
a = a ->next;
c = a;
}
else
{
c ->next = b;
b = b ->next;
c = b;
}
}
c ->next = a? a:b;
free(L2);
return ok;
}
status ShowList(LinkList L){
LNode *p = L->next;
while(p!=NULL){
printf("%d\n", p->data);
p = p->next;
}
return ok;
}
int main(){
LinkList L1, L2, L3;
InitList(L1);
InsertList(L1, 1, 666);
//ShowList(L);
InsertList(L1, 2, 888);
printf("L1:\n");
ShowList(L1);
// ElemType e;
//DeleteList(L, 1, e);
// printf("删除%d\n删除后:\n", e);
//ShowList(L);
//CreatList(L2, 2);
InitList(L2);
InsertList(L2, 1, 686);
InsertList(L2, 2, 868);
printf("L2:\n");
//printf("L2:\n");
ShowList(L2);
MergeList(L1,L2,L3);
printf("L3:\n");
ShowList(L3);
return 0;
}
逆序前:1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9->
逆序后:9-> 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1->
问题分析:通过参考资料可以发现,本问题的关键点在于链表合并的算法是否正确。代码中没有给出函数实现,因此需要根据题目的描述来编写算法。一般来说,可以用两个指针分别指向两个链表的头节点,将值较小的节点连接到结果链表的尾部,然后将该链表的头指针向后移动一个节点,继续比较两个链表的头节点,直到其中一个链表为空,将另一个链表的剩余节点直接连接到结果链表的尾部即可。
解决方案:我们可以在代码中加入一个函数去实现上述算法。
具体代码如下:
from typing import List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
在主函数中,首先创建两个链表,然后调用上面的函数来实现链表的合并,最后进行遍历输出新的链表即可。具体代码如下:
if __name__ == "__main__":
# 创建两个链表
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
# 调用函数合并链表
l3 = mergeTwoLists(l1, l2)
# 遍历链表输出结果
while l3:
print(l3.val, end=' ')
l3 = l3.next
参考资料:算法经典第四版 P561-P579,LeetCode官网代码。