首页 > 试题广场 >

合并两个有序的单链表

[编程题]合并两个有序的单链表

热度指数：3598 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个升序的单链表的头节点 head1 和 head2，请合并两个升序链表，合并后的链表依然升序，并返回合并后链表的头节点。

输入描述:

两个升序的单链表的头节点 head1 和 head2

输出描述:

在给定的函数内返回新链表的头指针。

示例1

输入

5
1 2 3 4 5
6 
7 8 9 10 11 12

输出

1 2 3 4 5 7 8 9 10 11 12

备注:

保证链表的长度不大于1000000

算法知识视频讲解

pein531

归并的思想合并链表

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] list1 = br.readLine().trim().split(" ");
        int m = Integer.parseInt(br.readLine().trim());
        String[] list2 = br.readLine().trim().split(" ");
        ListNode head1 = new ListNode(Integer.parseInt(list1[0]));
        ListNode head2 = new ListNode(Integer.parseInt(list2[0]));
        ListNode cur1 = head1, cur2 = head2;
        for(int i = 1; i < n; i++){
            cur1.next = new ListNode(Integer.parseInt(list1[i]));
            cur1 = cur1.next;
        }
        for(int i = 1; i < m; i++){
            cur2.next = new ListNode(Integer.parseInt(list2[i]));
            cur2 = cur2.next;
        }
        ListNode list = mergeLinkedList(head1, head2);
        while(list != null){
            System.out.print(list.val + " ");
            list = list.next;
        }
    }
    
    private static ListNode mergeLinkedList(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                cur.next = head1;
                head1 = head1.next;
            }else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        cur.next = head1 == null? head2: head1;
        return dummy.next;
    }
}

发表于 2021-06-01 22:20:09 回复(0)

C++

我要出去乱说

list_node * merge_list(list_node * head1, list_node * head2)
{
    list_node *head = new list_node(), *p = head;

    while (head1 != nullptr && head2 != nullptr)
    {
        if (head1->val < head2->val)
        {
            p = p->next = head1;
            head1 = head1->next;
        }
        else
        {
            p = p->next = head2;
            head2 = head2->next;
        }
    }

    if (head1 != nullptr) p->next = head1;
    if (head2 != nullptr) p->next = head2;

    return head->next;
}

发表于 2022-05-14 13:00:28 回复(0)

C/C++

nbgao

list_node * merge_list(list_node * head1, list_node * head2)
{
    list_node * head = new list_node();
    list_node *p = head;
    while(head1 && head2){
        if(head1->val < head2->val){
            p->next = head1;
            head1 = head1->next;
        }else{
            p->next = head2;
            head2 = head2->next;
        }
        p = p->next;
    }
    while(head1){
        p->next = head1;
        p = p->next;
        head1 = head1->next;
    }
    while(head2){
        p->next = head2;
        p = p->next;
        head2 = head2->next;
    }
    return head->next;
}

发表于 2020-06-10 00:59:52 回复(0)

牛客916673034号

边界总是超时有没有大佬知道怎么修改呀

import java.util.Scanner;

import java.io.*;

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

public class Main {

public static class ListNode {

int val;

ListNode next;

ListNode() {}

ListNode(int val) {

this.val = val;

}

ListNode(int val, ListNode next) {

this.val = val;

this.next = next;

}

public static ListNode move(ListNode listNode1, ListNode listNode2) {

ListNode newNode = new ListNode();

ListNode head1 = listNode1;

ListNode head2 = listNode2;

ListNode head3 = newNode;

while (head1 != null && head2 != null) {

if (head1.val > head2.val) {

head3.next = head2;

head2 = head2.next;

head3 = head3.next;

} else {

head3.next = head1;

head1 = head1.next;

head3 = head3.next;

}

if (head1 == null) head3.next = head2;

else if (head2 == null) head3.next = head1;

return newNode.next;

}

public static void main(String[] args) throws IOException {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

int[] list1 = new int[a];

for (int i = 0; i < a; i++) list1[i] = in.nextInt();

int b = in.nextInt();

int[] list2 = new int[b];

for (int i = 0; i < b; i++) list2[i] = in.nextInt();

ListNode listNode1 = new ListNode(list1[0]);

ListNode listNode2 = new ListNode(list2[0]);

ListNode head1 = listNode1;

ListNode head2 = listNode2;

for (int i = 1; i < a; i++) {

head1.next = new ListNode(list1[i]);

// System.out.println(listNode1.val);

head1 = head1.next;

}

for (int i = 1; i < b; i++) {

head2.next = new ListNode(list2[i]);

head2 = head2.next;

}

ListNode list = move(listNode1, listNode2);

while (list != null) {

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

list = list.next;

}

发表于 2023-04-13 23:56:58 回复(0)

Java

hugh98

为什么在边界运行总是超时？？？我吐了

发表于 2021-10-05 19:38:53 回复(0)

Python 3

毓毓子最可爱

len1=int(input())
list1=list(map(int,input().split()))
len2=int(input())
list2=list(map(int,input().split()))
#合并,并排序列表
ans=sorted(list1+list2)
print(' '.join(map(str,ans)))

发表于 2021-08-09 08:55:18 回复(0)

牛客277622865号

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

struct list_node{
    int val;
    struct list_node * next;
};


list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * merge_list(list_node * head1, list_node * head2)
{
    //////在下面完成代码
    list_node *head = new list_node();
    list_node *cur = head;
    bool flag = true;
    while (head1 != NULL || head2 != NULL) {
        if (head2 == NULL || (head1 != NULL && head1->val < head2->val)) {
            list_node *tmp = new list_node();
            tmp->val = head1->val;
            tmp->next = NULL;
            cur->next = tmp;
            cur = tmp;
            head1 = head1->next;
        } else {
            list_node *tmp = new list_node();
            tmp->val = head2->val;
            tmp->next = NULL;
            cur->next = tmp;
            cur = tmp;
            head2 = head2->next;
        }
    }
    return head->next;
}


void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}


int main ()
{
    list_node * head1 = input_list();
    list_node * head2 = input_list();
    list_node * new_head = merge_list(head1, head2);
    print_list(new_head);
    return 0;
}

发表于 2020-05-20 15:51:43 回复(0)

gapex

取head1和head2为头的两链表中，头结点值较小的那一个，插入结果链表

list_node * merge_list(list_node * head1, list_node * head2)
{
  list_node *head = nullptr;
  list_node **ptail = &head;
  while(head1 && head2){
      if(head1->val < head2->val){
          *ptail = head1;
          head1 = head1->next;
      }else{
          *ptail = head2;
          head2 = head2->next;
      }
      ptail = &((*ptail)->next);
      *ptail = nullptr;
  }
  *ptail = head1 ? head1 : head2;
  return head;
}

发表于 2020-05-08 21:46:01 回复(0)

北冥i鱼

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
    int data;
    struct LNode* next;
}LNode,*LinkList;

LinkList Init();
void GetNum(LinkList H,int n);
void Add(LinkList p1,LinkList p2);

int main(){
    LinkList p1,p2;
    int m,n;
    p1 = Init();
    p2 = Init();
    scanf("%d",&m);
    GetNum(p1,m);
    scanf("%d",&n);
    GetNum(p2,n);
    Add(p1,p2);
    p2 = p2->next;
    while(p2){
        printf("%d ",p2->data);
        p2 = p2->next;
    }
}
LinkList Init()
{
    LinkList H = (LinkList)malloc(sizeof(LNode));
    H->next = NULL;
    return H;
}
void GetNum(LinkList H,int n){
    LinkList p,q=H;
    int x;
    for(int i = 0; i < n; i++){
        scanf("%d",&x);
        p = (LinkList)malloc(sizeof(LNode));
        p->next = NULL;
        p->data = x;
        q->next = p;
        q = p;
    }
}
void Add(LinkList p1,LinkList p2){
    LinkList p = p2->next,q = p1->next,s=p2;
    while(p&&q){
        if (p->data <= q->data){
            s->next = p;
            s = p;
            p = p->next;
        }else{
            s->next = q;
            s = q;
            q = q->next;
        }
    }
    s->next = p ? p : q;
}

编辑于 2020-04-12 20:15:48 回复(0)

Era_Huang

import java.util.Scanner;

public class Main{
         public static int [] left;
      public static int [] right;
      public static int lPoint;
      public static int rPoint;
      public static int leftNumber;
      public static int rightNumber;

      public static boolean leftIsEmpty(){
      return lPoint >= leftNumber;
      }

      public static boolean rightIsEmpty(){
      return rPoint >= rightNumber;
      }

      public static void init()
      {
      Scanner scan = new Scanner(System.in);
      leftNumber = scan.nextInt();
      scan.nextLine();
      String[] temp1 = scan.nextLine().split(" ");


      rightNumber = scan.nextInt();
      scan.nextLine();
      String[] temp2 = scan.nextLine().split(" ");


      // 初始化对象
      left = new int[leftNumber];
      right = new int[rightNumber];
      lPoint = 0;
      rPoint = 0;

      for(int i=0; i<leftNumber; i++) {
          left[i] = Integer.parseInt(temp1[i]);
      }

      for(int i=0; i<rightNumber; i++) {
          right[i] = Integer.parseInt(temp2[i]);
      }
      }

      public static void main(String[] args){
      init();
      while(!leftIsEmpty() || !rightIsEmpty()){
      if(leftIsEmpty() && !rightIsEmpty()){
      System.out.print(right[rPoint] + " ");
      rPoint ++;

      }

      else if(!leftIsEmpty() && rightIsEmpty()){
      System.out.print(left[lPoint] + " ");
      lPoint ++;
      }

      else{
      if(left[lPoint] > right[rPoint]){
      System.out.print(right[rPoint] + " ");
      rPoint ++;
      }
      else{
      System.out.print(left[lPoint] + " ");
      lPoint ++;
      }
      }
      }
      }
}

发表于 2020-03-05 17:07:31 回复(0)

C/C++

流星心～

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
void PrintList( list<int>Li)
{
    for (list<int>::iterator it = Li.begin(); it != Li.end(); it++)
        cout << *it << " ";
}
int main()
{
        int n;
        cin >> n;
        list<int>L1;
        for (int i = 0; i<n; i++)
        {
            int a;
            cin >> a;
            L1.push_back(a);
        }
        int m;
        cin >> m;
        list<int>L2;
        for (int i = 0; i<m; i++)
        {
            int a;
            cin >> a;
            L2.push_back(a);
        }
        list<int>::iterator it1 = L1.begin();
        list<int>::iterator it2 = L2.begin();
        list<int>L3;
        for (int i = 0; i < m + n; i++)
        {
            if (it1 == L1.end() || it2 == L2.end())break;
            if (*it1 > *it2) {
                L3.push_back(*it2);
                it2++;
            }
            else
            {
                L3.push_back(*it1);
                it1++;
            }
        }
        if (it1 == L1.end()) {
            while (it2 != L2.end()) {
                L3.push_back(*it2);
                it2++;
            }
        }
        else
        {
            while (it1 != L1.end()) {
                L3.push_back(*it1);
                it1++;
            }
        }

    PrintList(L3);
    system("pause");
    return 0;
}

发表于 2020-03-01 11:25:16 回复(0)

EVANnnn1996

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node merge(Node head1, Node head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        Node head = new Node(-1);
        Node cur = head;
        while (head1 != null && head2 != null) {
            if (head1.value > head2.value) {
                cur.next = head2;
                head2 = head2.next;
            } else {
                cur.next = head1;
                head1 = head1.next;
            }
            cur = cur.next;
        }
        cur.next = head1 != null ? head1 : head2;
        return head.next;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int num1 = Integer.parseInt(bufferedReader.readLine());
        String[] number1 = bufferedReader.readLine().split(" ");
        int num2 = Integer.parseInt(bufferedReader.readLine());
        String[] number2 = bufferedReader.readLine().split(" ");
        Node head1 = listGenerator(num1, number1);
        Node head2 = listGenerator(num2, number2);
        Node head = merge(head1, head2);
        printList(head);
    }
}

不通过

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。点击对比用例标准输出与你的输出
case通过率为75.00%

发表于 2020-02-16 17:34:42 回复(0)

红玉圆

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

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &val);
        if (i == 1)
        {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else
        {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

list_node * merge_list(list_node * head1, list_node * head2)
{
    //////在下面完成代码

    list_node *head = new list_node;
    list_node *p1 = head1;
    list_node *p2 = head2;

    if (p1->val > p2->val)
    {
        head->val = p2->val;
        head->next = NULL;
        p2 = p2->next;
    }
    else
    {
        head->val = p1->val;
        head->next = NULL;
        p1 = p1->next;
    }
    list_node *cur_node = head;
    while (p1 && p2)
    {
        list_node * new_node = new list_node;

        if (p1->val > p2->val)
        {
            new_node->val = p2->val;
            new_node->next = NULL;
            cur_node->next = new_node;
            cur_node = new_node;
            p2 = p2->next;
        }
        else
        {
            new_node->val = p1->val;
            new_node->next = NULL;
            cur_node->next = new_node;
            cur_node = new_node;
            p1 = p1->next;
        }
    }
    while (p1)
    {
        list_node * new_node = new list_node;
        new_node->val = p1->val;
        new_node->next = NULL;
        cur_node->next = new_node;
        cur_node = new_node;
        p1 = p1->next;
    }
    while (p2)
    {
        list_node * new_node = new list_node;
        new_node->val = p2->val;
        new_node->next = NULL;
        cur_node->next = new_node;
        cur_node = new_node;
        p2 = p2->next;
    }
    return head;
}

void print_list(list_node * head)
{
    while (head != NULL)
    {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main()
{
    list_node * head1 = input_list();
    list_node * head2 = input_list();
    list_node * new_head = merge_list(head1, head2);
    print_list(new_head);
    return 0;
}

发表于 2019-10-22 19:54:32 回复(0)

Expecto_Patronum

struct valueCompare{//自定义比较函数
    bool operator()(const list_node* a,const list_node* b){
        return a->val>b->val;
    }
};
list_node * merge_list(list_node * head1, list_node * head2)
{
    list_node *resultHead=nullptr,*resultTail=nullptr;
    priority_queue<list_node*,vector<list_node*>,valueCompare> minHeap;//建立小顶堆
    minHeap.push(head1);
    minHeap.push(head2);
    while(!minHeap.empty()){
        auto node=minHeap.top();
        minHeap.pop();
        if(resultHead==NULL){//第一次循环
            resultHead=resultTail=node;
        }
        else{
            resultTail->next=node;
            resultTail=resultTail->next;
        }
        if(node->next){
            minHeap.push(node->next);
        }
    }
    return resultHead;
}

编辑于 2019-08-30 16:04:06 回复(0)

天命剑主

    if(head1==NULL){
        return head2;
    }
    if(head2==NULL){
        return head1;
    }
    list_node *h = NULL;
    list_node *t = NULL;
    list_node *p = head1;
    list_node *q = head2;
    if(p->val<q->val){
        h  = p;
        t = p;
        p = p->next;
    }else{
        h = q;
        t = q;
        q = q->next;
    }
    while(p!=NULL&&q!=NULL){
        if(p->val < q->val){
            t->next = p;
            t = p;
            p = p->next;
        }else{
            t->next = q;
            t = q;
            q = q->next;
        }
    }
    if(q == NULL){
        t->next = p;
    }else{
        t->next = q;
    }
    return h;

发表于 2019-08-26 17:07:55 回复(0)