LeetCode-021
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Solution
Java
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode solution=new ListNode(-1);
solution.next=l1;
ListNode node;
ListNode sol=solution;
while (l2!=null) {
if (solution.next==null) {
solution.next=l2;
break;
}
if (l2.val>solution.next.val)
solution=solution.next;
else {
node=solution.next;
solution.next=new ListNode(l2.val);
solution.next.next=node;
l2=l2.next;
}
}
return sol.next;
}
}
|
C
#orderList.h
struct ListNode {
int val;
struct ListNode *next;
};
int comp(int a,int b);
void initList(struct ListNode **L);
void printList(struct ListNode *L);
void orderInsert(struct ListNode *L,int e,int(*compare)(int a,int b));
void insertElement(struct ListNode** L);
void initOrderlist(struct ListNode** L);
struct ListNode* mergeTwoLists(struct ListNode** l1, struct ListNode* l2);
#orderList.c
#include "stdio.h"
#include "stdlib.h"
#include "orderList.h"
int comp(int a,int b){
return a-b;
}
int (*compare)(int a,int b) = ∁
void printList(struct ListNode* L){
struct ListNode* p=L;
printf("当前链表为：\n");
while (p->next!=NULL){
p=p->next;
printf("%d ",p->val);
}
printf("\n");
}
void initList(struct ListNode **L){
printf("初始化链表：\n");
struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode));
(*L)=p;p->val=-1;p->next=NULL;
int index=1;
int val=-1;
while(1) {
printf("退出请输入-1，请输入结点%d：\n",index);
scanf("%d",&val);
if (val==-1) break;
p->next=(struct ListNode*)malloc(sizeof(struct ListNode));
p->next->val=val;p->next->next=NULL;
p=p->next;
index++;
}
printList(*L);
}
void orderInsert(struct ListNode *L,int e,int(*compare)(int a,int b)){
struct ListNode* p=L;
struct ListNode* q=(struct ListNode*)malloc(sizeof(struct ListNode));
q->val=e;q->next=NULL;
while (1){
if (p->next==NULL){
p->next=q;
break;
}
if ((*compare)(p->next->val,e)<0)
p=p->next;
else{
q->next=p->next;
p->next=q;
break;
}
}
}
void insertElement(struct ListNode** L){
printf("在链表中插入结点：\n");
int val=-1;
while (1){
printf("退出请输入-1，请输入插入结点：\n");
scanf("%d",&val);
if (val==-1) break;
orderInsert(*L,val,compare);
}
printList(*L);
}
void initOrderlist(struct ListNode** L){
(*L)=(struct ListNode*)malloc(sizeof(struct ListNode));
(*L)->val=-1;(*L)->next=NULL;
printf("初始化有序链表：\n");
int index=1;
int val=-1;
while (1){
printf("退出请输入-1，请输入结点%d：\n",index);
scanf("%d",&val);
if (val==-1) break;
orderInsert(*L,val,compare);
index++;
}
printList(*L);
}
struct ListNode* mergeTwoLists(struct ListNode** l1, struct ListNode* l2){
while (l2->next!=NULL){
l2=l2->next;
int val=l2->val;
orderInsert(*l1,val,compare);
}
return *l1;
}
#main.c
#include "orderList.h"
int main(int argc,char* argv[]){
int op;
struct ListNode *head1;
struct ListNode *head2;
printf("请选择操作类型：1、构建有序表；2、构建并向有序表中插入元素；3、构建两个有序表并将其合并为同一个；4、退出：\n");
scanf("%d",&op);
switch (op){
case 1:{
initOrderlist(&head1);
break;
}
case 2:{
initOrderlist(&head1);
insertElement(&head1);
break;
}
case 3:{
initOrderlist(&head1);
initOrderlist(&head2);
printList(mergeTwoLists(&head1,head2));
break;
}
case 4:
exit(0);
}
return 0;
}
|
题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
总结：
执行用时2 ms，在所有 Java 提交中击败了95.30%的用户。
内存消耗36.3 MB，在所有 Java 提交中击败了87.29%的用户。
很简单的程序，后面补充递归算法，分别用Java和C实现。
记：
已经写过1,2,3,7,9,13,14,20,21,706十道，在写 Top-100-liked-questions ，账户页面 https://leetcode-cn.com/u/v2beach/ ，尝试在csdn记录，会努力找到每个题的最优解，欢迎互勉和监督。