首页 > 试题广场 >

链表合并

[编程题]链表合并
  • 热度指数:7388 时间限制: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
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)
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)
#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)
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)
#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)
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)
#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)

这种题就是拿来秀一把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)
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)
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)
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)
归并排序改编
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)
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)
//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)
fhfcnfcbhjfc
发表于 2022-03-25 18:55:23 回复(0)
zip(a,b)
发表于 2022-01-07 13:11:26 回复(0)
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)
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int _v):val(_v), next(nullptr) {}
    ListNode(int _v, ListNode* _l): val(_v), next(_l) {}
};

ListNode* mergeListNode(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr || l2 == nullptr) {
        return !l1 && !l2? nullptr : !l1? l2 : l1;
    }
    auto* head = new ListNode(-1, l1);
    ListNode* left = l1, *right = l2, *prev = head;
    while (left && right) {
        if (left -> val > right -> val) {
            ListNode* tmp = right -> next;
            prev -> next = right;
            right -> next = left;
            prev = right;
            right = tmp;
        } else {
            prev = left;
            left = left -> next;
        }
    }
    if (right) {
        prev -> next = right;
    }
    return head -> next;
}

ListNode* creatList(string s){
    stringstream ss(s);
    vector<int> a;
    int x;
    int idx = 0;
    ListNode* head, *tmp;
    while(ss >> x) {
        if (idx == 0) {
            head = new ListNode(x);
            tmp = head;
            ++idx;
            continue;
        }
        auto* cache = new ListNode(x);
        tmp -> next = cache;
        tmp = cache;
        ++idx;
    }
    tmp -> next = nullptr;
    return head;
}

int main() {
    ListNode *l1, *l2;
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    l1 = creatList(s1);
    l2 = creatList(s2);
    ListNode* res = mergeListNode(l1, l2);
    while (res) {
        cout << res -> val << " ";
        res = res -> next;
    }
    return 0;
}

发表于 2021-08-28 14:32:42 回复(0)