13008 - Merge Two Sorted Linked List   

Status  |  Limits Submit

Description

Given two sorted linked lists. Please Write a C program to merge them into one single sorted linked list.

In function.c, you only need to implement function merge_lists(), and return the head pointer of the merged list.

function.c (OJ會跑板請記得code複製完要自己排版)

#include "function.h"
 
/************************ Node ************************/
Node *create_node(int data)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
 
    return node;
}
 
/************************ SLL ************************/
SinglyLinkedList *create_singlyLinkedList(int hasInput)
{
    SinglyLinkedList *list = (SinglyLinkedList *)malloc(sizeof(SinglyLinkedList));
    list->head = NULL;
 
    if (hasInput)
    {
        int len;
        scanf("%d", &len);
        for (int i = 0; i < len; i++)
        {
            int data;
            scanf("%d", &data);
            insert_node(list, data);
        }
    }
 
    return list;
}
 
void insert_node(SinglyLinkedList *list, int data)
{
    Node *node = create_node(data);
 
    if (list->head == NULL)
    {
        list->head = node;
    }
    else
    {
        Node *tmp = list->head;
        while (tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        tmp->next = node;
    }
}
 
void print_list(Node *list_node)
{
    if (list_node == NULL)
    {
        printf("None\n");
        return;
    }
 
    Node *tmp = list_node;
    for (; tmp->next != NULL; tmp = tmp->next)
    {
        printf("%d ", tmp->data);
    }
    printf("%d\n", tmp->data);
}
 
// Complete the compare_lists function below.
Node *merge_lists(Node *list1_node, Node *list2_node)
{
    if (list1_node == NULL || list2_node == NULL)
        return list1_node == NULL ? list2_node : list1_node;
 
    // Todo
}

Input

Input follows below format:

len1

n1 n2 n3 n4 ….

len2

m1 m2 m3 m4 ….

All len1, len2, n1~ and m1~ are integers. len1 represents the length of the first linked list, also indicates the total number of the data in the next line.

Note:

  1. 10 >= len1, len2 >= 0.
  2. 32767 >= n1~, m1~ >= -32768.

 

Example:

3

1 2 7

4

2 2 3 9

 

List1: 1 -> 2 -> 7 -> NULL

List2: 2 -> 2 -> 3 -> 9 -> NULL

List Merge: 1 -> 2 -> 2 -> 2 -> 3 -> 7 -> 9 -> NULL

Output

N1 N2 N3 N4 …

Note:

  1. Need to have a return value('\n') at the end of your string.
  2. If the merged linked list is empty, print(“None\n”).

Sample Input  Download

Sample Output  Download

Partial Judge Code

13008.c

Partial Judge Header

13008.h

Tags




Discuss