链表合并_蘑菇街笔试题

Jared_VIP

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

这里贴一下我的代码这道题很多人都是误解了题目的意思他要的是链表所以应该这样写，希望能顶上去麻烦大家了

发表于 2019-08-11 10:53:29 回复(0)

勇敢牛牛，不怕困难！

#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');
}

发表于 2021-07-04 13:19:06 回复(0)

LeehomWang

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());
    }
}

发表于 2020-05-15 09:43:42 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int x;
    vector<int> v;
    while(cin>>x)
        v.push_back(x);
    sort(v.begin(), v.end());
    if(!v.empty()){
        for(int i=0;i<v.size();i++){
            if(i==v.size()-1)
                cout<<v[i]<<endl;
            else
                cout<<v[i]<<" ";
        }
    }
    return 0;
}

发表于 2019-12-04 23:57:08 回复(0)

xiaojia123

3ms

376k

C

两个有序链表合并，有一点处理技巧，就是通过交换链表指针，确保head1链表的首节点元素小于等于head2链表的首节点元素，这样可以简化合并时以第一个链表为基准还是第二个链表为基准的判断

#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;
    }
}

编辑于 2019-10-20 12:11:45 回复(0)

C/C++

昔遥暮云

#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;
}

发表于 2019-10-10 20:26:13 回复(0)

LitterF

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()

发表于 2019-10-08 16:59:39 回复(0)

活泼的土拨鼠在吃瓜

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))

发表于 2019-09-04 21:58:34 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    vector<int>res;
    while(cin>>n)
        res.push_back(n);
    sort(res.begin(),res.end());
    if(!res.empty())
    {
        cout<<res[0];
        for(int i=1;i<res.size();i++)
            cout<<" "<<res[i];
        cout<<endl;
    }
    return 0;
}

发表于 2019-07-03 10:23:47 回复(1)

keashem

这种题就是拿来秀一把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());
    }
}

发表于 2019-08-05 12:42:35 回复(0)

Python

Chrety

n = map(int, raw_input().split())
m = map(int, raw_input().split())
n += m
n.sort()
for i in n :
    print i,

发表于 2019-07-20 07:56:47 回复(2)

Java

呃。。。

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]+" ");
    }
}

发表于 2019-08-14 15:17:02 回复(0)

Python

深海水蜇

a,b=list(reversed(list(map(int,input().split())))),list(reversed(list(map(int,input().split()))))
print (' '.join([str(a.pop()) if (a and (not b or a[-1]<b[-1])) else str(b.pop()) for _ in range(len(a)+len(b))]))

发表于 2019-06-29 15:09:36 回复(1)

C

徐文达

#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;
}

编辑于 2024-03-30 10:38:34 回复(0)

Java

牛客293567648号

归并排序改编

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

Node list1 = createList(in.nextLine().split(" "));

Node list2 = createList(in.nextLine().split(" "));

Node res = mergeList(list1, list2);

while(res != null) {

System.out.print(res.value + " ");

res = res.next;

}

public static Node mergeList(Node o1, Node o2) {

Node tmp1 = o1;

Node tmp2 = o2;

Node pre = new Node(0);

Node res = pre;

if(tmp1 == null) {

return tmp2;

}

if(tmp2 == null) {

return tmp1;

}

while(tmp1 != null && tmp2 != null) {

if(tmp1.value < tmp2.value) {

res.next = tmp1;

res = res.next;

tmp1 = tmp1.next;

} else {

res.next = tmp2;

res = res.next;

tmp2 = tmp2.next;

}

if(tmp1 != null) {

res.next = tmp1;

}

if(tmp2 != null) {

res.next = tmp2;

}

return pre.next;

}

public static Node createList(String[] str) {

if(str == null || str.length == 0) {

return null;

}

Node pre = new Node(0);

Node list = pre;

for(int i = 0; i < str.length; i++) {

list.next = new Node(Integer.parseInt(str[i]));

list = list.next;

}

return pre.next;

}

class Node{

int value;

Node next;

Node() {

}

Node(int value) {

this.value = value;

}

发表于 2023-06-21 01:53:19 回复(0)

Go

小谷围做题家

package main

import (
    "fmt"
    "sort"
)

func main() {
    var x int
    arr:=[]int{}
    for{
        _,ok:=fmt.Scan(&x)
        if ok!=nil{
            break
        }
        arr=append(arr,x)
    }
    sort.Ints(arr)
    for i:=0;i<len(arr);i++{
        fmt.Printf("%v ",arr[i])
    }
}

发表于 2023-03-21 14:55:44 回复(0)

Java

wqz579

//ACM模式，就是麻烦一点，需要自己从标准输入提取数值再建立链表

//采用三指针迭代法

import java.util.Scanner;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

String s1=in.nextLine();

String s2=in.nextLine();

ListNode list1=getListNode(s1);

ListNode list2=getListNode(s2);

ListNode dummy=new ListNode();

ListNode prev=dummy;

while(list1!=null && list2!=null)

{

if(list1.val<=list2.val)

{

prev.next=list1;

list1=list1.next;

}

else

{

prev.next=list2;

list2=list2.next;

}

prev=prev.next;

}

prev.next = list1==null?list2:list1;

dummy=dummy.next;

while(dummy!=null)

{

System.out.print(dummy.val+" ");

dummy=dummy.next;

}

public static ListNode getListNode(String s)

{

ListNode dummy=new ListNode();

ListNode prev=dummy;

String[] c=s.split(" ");

int n=c.length;

for(int i=0;i<n;++i)

{

ListNode list=new ListNode(Integer.valueOf(c[i]));

prev.next=list;

prev=prev.next;

}

return dummy.next;

}

class ListNode

{

int val;

ListNode next;

public ListNode(){}

public ListNode(int val)

{

this.val=val;

}

public ListNode(int val, ListNode next)

{

this.val=val;

this.next=next;

}

发表于 2023-03-09 10:08:20 回复(0)

牛马中的233

fhfcnfcbhjfc

发表于 2022-03-25 18:55:23 回复(0)

disarif

zip(a,b)

发表于 2022-01-07 13:11:26 回复(0)

Mask_5563

s1 = list(map(int, input().split()))
s2 = list(map(int, input().split()))
s = s1 + s2
print(' '.join(map(str,sorted(s))))

发表于 2021-09-30 19:24:16 回复(0)

链表合并

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题