我要招人

去企业版

首页 > 试题广场 >

链表合并

[编程题]链表合并

热度指数：7429 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请编写一段代码，实现两个单向有序链表的合并

输入描述:

第一行一个链表，如1 2 3 4 5

第二行一个链表，如2 3 4 5 6

输出描述:

输出：1 2 2 3 3 4 4 5 5 6

示例1

输入

1 2 3 4 5
2 3 4 5 6

输出

1 2 2 3 3 4 4 5 5 6

算法知识视频讲解

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)

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)

Java

飒飒的收到Z传说中

太简单啦，作为链表的练手题最好不过了。其实要是够大胆，可以直接先把数字排序再创建链表就更简单了。可惜不符合题意。上代码。。。。

import java.util.*;
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        ListNode list1 = createList(sc.nextLine().split(" "));
        ListNode list2 = createList(sc.nextLine().split(" "));
        ListNode list = combineList(list1,list2);
        while(list!=null){
            System.out.print(list.val+" ");
            list=list.next;
        }
    }
    public static ListNode createList(String[] str){
    	if(str==null||str.length==0)
    		return null; 
    	ListNode pre = new ListNode(0);
    	ListNode list = pre;
    	for(int i=0;i<str.length;i++) {
    		list.next= new ListNode(Integer.parseInt(str[i]));
    		list=list.next;
    	}
		return pre.next;
    }
    public static ListNode combineList(ListNode list1,ListNode list2){
    	if(list1==null) return list2;
    	if(list2==null) return list1;
    	ListNode pre = new ListNode(0);
    	ListNode list=pre;
    	while(list1!=null||list2!=null) {
    		if(list1.val<list2.val) {
    			list.next=new ListNode(list1.val);
    			list1=list1.next;
    		}
    		else {
    			list.next = new ListNode(list2.val);
    			list2=list2.next;
    		}
    		list=list.next;
    		if(list1==null) list.next=list2;
    		if(list2==null) list.next=list1;
    	}
		return pre.next;
        
    }
}

发表于 2019-09-10 22:07:57 回复(1)

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)