class ListNode(object): def __init__(self,x=None): self.val = x self.next = None class Solution(object): def mergeTwoLists(l1,l2): """ :param l1: ListNode :param l2: ListNode :return: ListNode """ if not l1 and not l2: return None if not l1: return l2 if not l2: return l1 l3 = ListNode() l3_head = l3 while l1 is not None and l2: if l1.val<=l2.val: l3.next = l1 l1 = l1.next else: l3.next = l2 l2 = l2.next l3 = l3.next if l1 is not None: l3.next = l1 else: l3.next = l2 return l3_head.next def Create(list1,list2): temp_node1 = ListNode() node1 = temp_node1 temp_node2 = ListNode() node2 = temp_node2 for i in list1: if not temp_node1.val: temp_node1.val = i node1 = temp_node1 else: temp_node1.next = ListNode(i) temp_node1 = temp_node1.next for i in list2: if not temp_node2.val: temp_node2.val = i node2 = temp_node2 else: temp_node2.next = ListNode(i) temp_node2 = temp_node2.next return (node1,node2) if __name__ == '__main__': list1 = list(map(int,input().split())) list2 = list(map(int,input().split())) # print(list1) # print(list2) node1,node2 = Create(list1,list2) l3_node = mergeTwoLists(node1,node2) while l3_node: print(l3_node.val,end=' ') l3_node = l3_node.next
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef int ElemType; typedef struct ListNode { ElemType val; struct ListNode* next; } ListNode; // =============== function prorotype =============== ListNode* createList(void); ListNode* mergeTwoSortedList(ListNode* l1, ListNode* l2); // debug helper function void printList(ListNode* head); int main(const int argc, const char** argv) { ListNode *l1 = createList(), // 创建第一个 *l2 = createList(), *ret = mergeTwoSortedList(l1, l2); return printList(ret), 0; } ListNode* createList(void) { ListNode dummy = {.val = 0, .next = NULL}; ListNode *tail = &dummy, *new_node; char *tmp[500], *tok ; gets(tmp); tok = strtok(tmp, " "); while (tok) { new_node = malloc(sizeof(ListNode)); new_node->val = atoi(tok); new_node->next = NULL; tail = tail->next = new_node; tok = strtok(NULL, " "); } return dummy.next; } ListNode* mergeTwoSortedList(ListNode* l1, ListNode* l2) { ListNode dummy = {.val = 0, .next = NULL}; ListNode* p = &dummy; while (l1 && l2) { if (l1->val < l2->val) { p = p->next = l1; l1 = l1->next; } else { p = p->next = l2; l2 = l2->next; } } p->next = l1 ? l1 : l2; return dummy.next; } void printList(ListNode* head) { while (head) { printf("%d", head->val); if (head->next) putchar(32); // ASCII CODE 32 == space head = head->next; } putchar('\n'); }
import java.io.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String[] str1=br.readLine().split(" "); String[] str2=br.readLine().split(" "); StringBuffer sb=new StringBuffer(); int i=0; int j=0; while(i<str1.length&&j<str2.length){ if(Integer.parseInt(str1[i])<Integer.parseInt(str2[j])){ sb.append(str1[i]+' '); i++; }else{ sb.append(str2[j]+' '); j++; } } if(i<str1.length) for(int t=i;t<str1.length;t++) sb.append(str1[t]+' '); if(j<str2.length) for(int t=j;t<str2.length;t++) sb.append(str2[t]+' '); System.out.println(sb.toString().trim()); } }
3ms | 376k | C |
#include <stdio.h> #include <stdlib.h> typedef struct Node{ int num; struct Node* next; }Node, *List; int main(){ List head1 = NULL; List tail1 = NULL; List head2 = NULL; List tail2 = NULL; int n; while(1){ scanf("%d", &n); Node* node = malloc(sizeof(Node)); node->num = n; if(head1 == NULL){ head1 = tail1 = node; node->next = NULL; } else{ node->next = NULL; tail1->next = node; tail1 = node; } if(getchar() == '\n'){ break; } } while(1){ scanf("%d", &n); Node* node = malloc(sizeof(Node)); node->num = n; if(head2 == NULL){ head2 = tail2 = node; node->next = NULL; } else{ node->next = NULL; tail2->next = node; tail2 = node; } if(getchar() == '\n'){ break; } } List tmp; if(head1->num > head2->num){ //使得head1指向链表的第一个元素小于等于head2指向链表的第一个元素 tmp = head1; head1 = head2; head2 = tmp; } List p1 = head1; List p2 = head2; while(p1->next != NULL && p2 != NULL){ if(p1->next->num <= p2->num){ p1 = p1->next; } else{ //将p2插入到p1上 tmp = p2->next; p2->next = p1->next; p1->next = p2; p1 = p1->next; p2 = tmp; } } if(p2 != NULL){ p1->next = p2; } p1 = head1; while(p1 != NULL){ printf("%d ", p1->num); p1 = p1->next; } }
#include <bits/stdc++.h> using namespace std; struct node{ int value; node *next; }; node* creatlist(const vector<int> &arr){ node *head=nullptr,*end=nullptr; node *pre; if(head==nullptr){ head=new node; head->value=arr[0]; pre=head; } for(int i=1;i<arr.size();i++){ end=new node; end->value=arr[i]; end->next=nullptr; pre->next=end; pre=pre->next; } return head; } node* mergelist(node* head1,node* head2){ node *p1=head1,*p2=head2,*head; node *pre,*next; head = head1->value<=head2->value ? head1:head2; while(p1!=nullptr&&p2!=nullptr){ if(p1->value<=p2->value){ pre=p1; p1=p1->next; } else{ next=p2->next; pre->next=p2; p2->next=p1; pre=p2; p2=next; } } pre->next= p1==nullptr ? p2:p1; return head; } int main(){ node *head1,*head2; int value; vector<int> arr1,arr2; while(cin>>value){ arr1.push_back(value); if(cin.get()=='\n') break; } while(cin>>value){ arr2.push_back(value); if(cin.get()=='\n') break; } head1=creatlist(arr1); head2=creatlist(arr2); node *p=mergelist(head1,head2); while(p!=nullptr){ cout<<p->value<<" "; p=p->next; } return 0; }
class ListNode: def __init__(self,val,next = None): self.val = val self.next = next def print(self): res = [self.val] cur = self.next while cur: res.append(cur.val) cur = cur.next print(' '.join(map(str,res))) def merge(a,b): new = ListNode(-1) cur = new while a and b: if a.val<=b.val: cur.next = a a = a.next cur = cur.next else: cur.next = b b = b.next cur = cur.next if a: cur.next = a if b: cur.next = b return new.next aa = list(map(int,input().split())) bb = list(map(int,input().split())) a,b = ListNode(-1),ListNode(-1) cur_a,cur_b = a,b for i in aa: cur_a.next = ListNode(i) cur_a = cur_a.next for i in bb: cur_b.next = ListNode(i) cur_b = cur_b.next a,b=a.next,b.next c = merge(a,b) c.print()
class Node: def __init__(self, x): self.val = x self.next = None def create_linked_list(nums1, nums2): cur1 = head1 = Node(nums1[0]) cur2 = head2 = Node(nums2[0]) for num in nums1[1:]: cur1.next = Node(num) cur1 = cur1.next for num in nums2[1:]: cur2.next = Node(num) cur2 = cur2.next return head1, head2 def merge(head1, head2): dummy = Node(-1) cur = dummy while head1 and head2: if head1.val <= head2.val: cur.next = head1 head1 = head1.next else: cur.next = head2 head2 = head2.next cur = cur.next if head1: cur.next = head1 elif head2: cur.next = head2 ans = [] cur = dummy.next while cur: ans.append(str(cur.val)) cur = cur.next return ' '.join(ans) nums1 = list(map(int, input().split())) nums2 = list(map(int, input().split())) head1, head2 = create_linked_list(nums1, nums2) print(merge(head1, head2))
这种题就是拿来秀一把java lambda表达式的
import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Scanner; import java.util.stream.Collectors; import static java.lang.System.in; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(in); List<Integer>list = Arrays.asList(sc.nextLine().split(" ")).stream().map(Integer::parseInt).collect(Collectors.toList()); list.addAll(Arrays.asList(sc.nextLine().split(" ")).stream().map(Integer::parseInt).collect(Collectors.toList())); Collections.sort(list); System.out.print(list.get(0)); list.subList(1,list.size()).stream().map((o1)->{ System.out.print(" "+o1); return 0; }).collect(Collectors.toList()); } }
public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String[] s1 = in.nextLine().split(" "); String[] s2 = in.nextLine().split(" "); int[] a = new int[s1.length]; int[] b = new int[s2.length]; int[] t = new int[s1.length+s2.length]; for (int i=0;i<s1.length;i++){ a[i] = Integer.parseInt(s1[i]); } for (int i=0;i<s2.length;i++){ b[i] = Integer.parseInt(s2[i]); } int i=0,j=0,k=0; while (i<a.length && j<b.length){ if (a[i] < b[j]) t[k++] = a[i++]; else t[k++] = b[j++]; } while (i < a.length) t[k++] = a[i++]; while (j < b.length) t[k++] = b[j++]; for(i=0;i<t.length;i++) System.out.print(t[i]+" "); } }
#include <stdio.h> #include <stdlib.h> //定义链表结点 typedef struct ListNode { int val; struct ListNode* next; }ListNode; void ListAdd(ListNode** tail, ListNode* node) { (*tail)->next = node; *tail = node; } //合并2个有序链表 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { //判断是需要进行排序 if (!list1) { return list2; } if (!list2) { return list1; } //创建一个新链表,并初始化head、tail为NULL ListNode* head = NULL; ListNode* tail = NULL; //遍历2个链表,同时进行比较,将val较小的结点连接至新链表中 while (list1 && list2) { if (list1->val > list2->val) { //将list2链接至新链表 if (head == NULL) { head = tail = list2; } else { ListAdd(&tail, list2); } list2 = list2->next; } else { //将list1链接至新链表 if (head == NULL) { head = tail = list1; } else { ListAdd(&tail, list1); } list1 = list1->next; } } //链接剩余结点 if (!list1) { //链接list2 ListAdd(&tail, list2); } else { //链接list1 ListAdd(&tail, list1); } return head; } //创建新结点,返回新结点地址 ListNode* ListBuyNode(int x) { //创建新结点 ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); if (!newNode) { perror("malloc fail!"); exit(1); } newNode->val = x; newNode->next = NULL; return newNode; } //打印链表 void ListPrint(ListNode* phead) { //判断是否需要打印,以免后续解引用时造成越界访问 if (phead == NULL) { return; } ListNode* pcur = phead; while (pcur != NULL) { printf("%d ", pcur->val); pcur = pcur->next; } } //释放链表 void ListFree(ListNode* phead) { //判断是否有结点以供释放 if (phead) { return; } ListNode* pcur = phead; ListNode* prev = NULL; while (pcur != NULL) { prev = pcur; pcur = pcur->next; free(prev); } } int main() { ListNode* head1 = NULL; ListNode* head2 = NULL; ListNode* tail1 = NULL; ListNode* tail2 = NULL; ListNode* mergeHead = NULL; int input = 0; char judge = 0; //录入链表1 judge = 1; while (judge != '\n') { scanf("%d", &input); judge = getchar(); if (head1 == NULL) { //链表为空时,同时更新头结点指针 head1 = tail1 = ListBuyNode(input); } else { //链表不为空,只更新尾结点指针即可 tail1->next = ListBuyNode(input); tail1 = tail1->next; } } //录入链表2 judge = 1; while (judge != '\n') { scanf("%d", &input); judge = getchar(); if (head2 == NULL) { //链表为空时,同时更新头结点指针 head2 = tail2 = ListBuyNode(input); } else { //链表不为空,只更新尾结点指针即可 tail2->next = ListBuyNode(input); tail2 = tail2->next; } } //合并链表 mergeHead = mergeTwoLists(head1, head2); //打印链表 ListPrint(mergeHead); //释放链表 ListFree(mergeHead); return 0; }