Объединение двух отсортированных связанных списков

Question

Это один из вопросов программирования, заданных во время письменного теста от Microsoft. Я даю вопрос и ответ, который я придумал. Вещи мой ответ, хотя выглядит всеобъемлющим (по крайней мере для меня), я чувствую, что количество строк может быть уменьшено. Это было задано в C, и я человек Java, но мне удалось его кодировать (мой ответ может содержать слишком много синтаксисов, подобных Java)

Хорошо, вот вопрос.

У вас есть два списка, которые уже отсортированы, вы должны объединить их и вернуть новый список без каких-либо новых дополнительных узлы. Возвращаемый список должен быть отсортировано также.

Подпись метода:

Node* MergeLists(Node* list1, Node* list2);

struct Node{
    int data;
    Node *next;
}

Вот решение, которое я придумал,

Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    if(list1 == null && list2 ==null){//if both are null, return null
        return null;
    }
    if(list1 == null){//if list1 is null, simply return list2
        return list2;
    }
    if(list2 == null){//if list2 is null, simply return list1
        return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList = list2;
    }
    while(list1!=null && list2!=null){
        if(list1.data < list2.data){
            mergedList->next = list1;
            list1 = list1->next;
        }else{
            mergedList->next = list2;
            list2 = list2->next;
        }
    }
    if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
        mergedList->next = list2;
    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
        mergedList->next = list1;
    }
    return mergedList;
}

Я очень уверен, что это можно улучшить. Пожалуйста, помогите мне найти, какие строки избыточно я добавил. Пожалуйста, не стесняйтесь критиковать мои синтаксические ошибки и логику.

Спасибо!

Answer 1

Самая яркая ошибка в вашем цикле: вы продолжаете переписывать mergedList-> next, теряя ранее добавленный узел То есть ваш возвращаемый список никогда не будет содержать более двух узлов, независимо от ввода ...

Прошло много времени с тех пор, как я сделал C, но я сделал бы это следующим образом:

Node* merge(Node* list1, Node* list2) {
    Node* merged = null;
    Node** tail = &merged;

    while (list1 && list2) {
        if (list1->data < list2->data) {
            *tail = list1;
            list1 = list1->next;
        } else {
            *tail = list2;
            list2 = list2->next;
        }
        tail = &((*tail)->next);
    }
    *tail = list1 ? list1 : list2;
    return merged;
}

Answer 2

Ваш код перегружен if -ами, вставленными для обработки «особых» случаев, что сильно его раздувает и затрудняет чтение. Обычно это происходит, когда вы решаете обрабатывать особые случаи «по коду», а не находите способ обрабатывать их «по данным». В заявлении, приписываемом Дэвиду Уилеру, говорится: «Все проблемы в информатике могут быть решены с помощью другого уровня косвенности». Этот «дополнительный уровень косвенности» обычно очень хорошо работает со списками, помогая значительно уменьшить беспорядок, создаваемый этими if s.

Чтобы проиллюстрировать вышесказанное, вот как будет выглядеть мой код

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

Некоторые могут утверждать, что использование дополнительного уровня косвенности в указателе pnext на самом деле делает код более трудным для чтения. Я бы согласился, что для новичка такой подход может представлять некоторые трудности, но для опытного программиста это должно быть легко усваиваемо как идиома.

Answer 3

Мой дубль, с тестовым набором

Пока что все ответы были интересными и хорошо сделаны. Вполне возможно, что это больше похоже на то, что хотел бы видеть интервьюер с DRY / DIE и TDD : -)

#include <stdio.h>

typedef struct ns {
    int data;
    struct ns *next;
} Node;

Node l1[] = {
  { 1, &l1[1] },
  { 3, &l1[2] },
  { 5, &l1[3] },
  { 7, &l1[4] },
  { 9, &l1[5] },
  {11, 0 },
};

Node l2[] = {
  { 2, &l2[1] },
  { 4, &l2[2] },
  { 6, 0 },
};

Node* MergeLists(Node* list1, Node* list2) {
  Node *t, **xt;
  for(xt = &t; list1 || list2;) {
    Node **z = list1 == NULL ? &list2 :
               list2 == NULL ? &list1 :
               list1->data < list2->data ? &list1 : &list2;
    *xt = *z;
     xt = &(*z)->next;
    *z  = *xt;
  }
  *xt = NULL;
  return t;
}

int main(void) {
  for(Node *t = MergeLists(l1, l2); t; t = t->next) 
    printf("%d\n", t->data);
  return 0;
}

Answer 4

Это не становится более элегантным, чем это:

Node* merge2(Node* n1, Node* n2) {
    n1->next = merge(n1->next, n2);
    return n1;
}

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
           (n1->data < n2->data) ?
               merge2(n1, n2) :
               merge2(n2, n1);
}

Предполагая, что вы понимаете рекурсию, это так же ясно, как и получается.

---

Я должен отметить, что это хорошо только для ответа на собеседование (где, по-видимому, демонстрация ясности мышления оказывает большее влияние, чем просто демонстрация того, что вы умеете писать программы). На практике вам не захочется объединять этот способ, поскольку он использует O(n) глубину стека, что, вероятно, приведет к переполнению стека. Кроме того, это не хвостовая рекурсия, поэтому она не оптимизируется компилятором.

Answer 5

Разделяй и властвуй

(т. Е. MergeSort )

Answer 6

Используйте рекурсию. Код выглядит следующим образом:

ListNode* mergeTwoSortedLists(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1, pHead2->m_pNext);
    }

    return pMergedHead;
}

Answer 7

Таким образом, объединяя полиген с AndreyT, мы получаем:

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
             (n1->data < n2->data) ? 
               (n1->next = merge(n1->next, n2), n1) : 
               (n2->next = merge(n2->next, n1), n2)}

Я не могу претендовать на кредит за этот, но он самый краткий и показывает симметрию между двумя аргументами, не вводит каких-либо неясных вспомогательных функций. Я не уверен, что оптимизирующий компилятор увидит здесь хвостовую рекурсию, но я вижу. Отступ - последний штрих.

Answer 8

//I have used recursions .
//Sorry for such a long code.
//:) it works,hope it helps.
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node{
    int data;
    struct node *next ;
};
struct node *start1=NULL,*start2=NULL;
struct node*start=NULL;
struct node *create_ll1(struct node *start);
struct node *create_ll2(struct node *start);
void sorted_ll(struct node* node1,struct node* node2);

struct node *display(struct node *start);
void p(struct node*);
main(){
    start1=create_ll1(start1);
    start2=create_ll2(start2);
    //start1=display(start1);
    printf("\n");
    //start2=display(start2);
    sorted_ll(start1,start2);
    //start=display(start);


}
struct node *create_ll1(struct node *start1){
    struct node *ptr,*new_node;
    int num;
    printf("Enter -1 for ending \n");
    printf("Enter data for list 1: \n");
    scanf("%d",&num);
    while(num!=-1){
        new_node=(struct node *)malloc(sizeof(struct node));
        new_node->data=num;
        if(start1==NULL){
            new_node->next=NULL ;
            start1=new_node;
        }
        else{
            ptr=start1 ;
            while(ptr->next!=NULL)
            ptr=ptr->next;
            ptr->next=new_node;
            new_node->next=NULL ;
        }
        printf("Enter data: \n");
        scanf("%d",&num);
    }
    return start1;

}
struct node *create_ll2(struct node *start2){
    struct node *ptr,*new_node;
    int num;
    printf("Enter -1 for ending \n");
    printf("Enter data for list 2: \n");
    scanf("%d",&num);
    while(num!=-1){
        new_node=(struct node *)malloc(sizeof(struct node));
        new_node->data=num;
        if(start2==NULL){
            new_node->next=NULL ;
            start2=new_node;
        }
        else{
            ptr=start2 ;
            while(ptr->next!=NULL)
            ptr=ptr->next;
            ptr->next=new_node;
            new_node->next=NULL ;
        }
        printf("Enter data: \n");
        scanf("%d",&num);
    }
    return start2;

}

struct node *display(struct node *start){
    struct node *ptr;
    ptr=start;
    while(ptr->next!=NULL){
        printf("\t %d",ptr->data);
        ptr=ptr->next;
    }
        printf("\t %d",ptr->data);
        printf("\n");


    return start ;
}
void sorted_ll(struct node* node1,struct node* node2)
{
    if(!node1){
        p(node2);
        exit(0);
    }
    else if(!node2){
        p(node1);
        exit(0);
    }
    if(node1->data<node2->data){
        printf("%d\t",node1->data);
        sorted_ll(node1->next,node2);


    }
    else{
        printf("%d\t",node2->data);
        sorted_ll(node1,node2->next);
    }
}
void p(struct node* pme){
    while(pme->next!=NULL){
        printf("%d \t",pme->data);
        pme=pme->next;
    }
    printf("%d",pme->data);

}

Answer 9

Вы можете использовать Java 8, Stream API для объединения, получения Distinct и сортировки.Ниже приведен пример кода для сортировки и объединения двух списков с целочисленными элементами

List<Integer> list1= Arrays.asList(2,3,5,8);
List<Integer> list2 = Arrays.asList(3,6,8);

List<Integer> finalList = new ArrayList<>();
finalList.addAll(list1);
finalList.addAll(list2);

List<Integer>  mergeSortedList = 
  finalList.stream()
    .distinct()
    .sorted()
    .collect(Collectors.toList());
System.out.println(mergeSortedList);

Answer 10

Вы можете использовать рекурсию:

Node* MergeLists(Node *headA, Node* headB)
{

if(headA==NULL){
    return headB;
}else if(headB ==NULL){
    return headA;
}
Node* head = NULL;
if(headA->data <= headB->data){
    head= headA;
    head->next = MergeLists(headA->next,headB);
}else{
    head= headB;
    head->next = MergeLists(headA,headB->next);
}
 return head;
}