Слияние двух отсортированных списков по связанным спискам

Question

Я сгруппировал два отсортированных списка, отсортированные по возрастанию. Я использую две функции для выполнения этой задачи:

1. Первый узел * MergedSort (Node * а, узел * б), который занимает головной узел обоих отсортированных списков и объединяет их вместе.

2. И еще одна функция полезности void MoveNode (Node ** dest, Node ** source), которая берет главный узел связанного с источником списка и помещает его поверх списка адресатов. И заставляет голову источника связанного списка указывать на следующий элемент.

Вот мой код для выполнения этой задачи:

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

void MoveNode(Node **dest, Node **source){ 
    Node *newNode = *source; 
    //Now source points to its second node; 
    *source = newNode->next; 
    //Connecting newNode to dest. 
    newNode->next = *dest; 
    //Now destination head points to newNode 
    *dest = newNode; 
    return; 
} 

Node *MergedSort(Node *a, Node *b){ 
    Node dummy; 
    Node *tail = &dummy; 
    dummy.next = NULL; 

    while(1){ 
      if (a == NULL){ 
        tail->next = b; 
        break; 
      } 
      else if (b == NULL){ 
        tail->next = a; 
        break; 
      } 
      else if (a->data < b->data){ 
        MoveNode(&(tail->next), &a); 
      } 
      else{ 
        MoveNode(&(tail->next), &b); 
      } 
      tail = tail->next; 
    } 
    return (dummy.next); 
} 

Теперь проблема заключается в этом, если я делаю небольшое изменение этого кода, то есть определить манекен быть указателем на узел, это дает me segmentation fault. Это ошибочный код, только с одним небольшим изменением, декларация манекена теперь Node * манекен:

void MoveNode(Node **dest, Node **source){ 
    Node *newNode = *source; 
    //Now source points to its second node; 
    *source = newNode->next; 
    //Connecting newNode to dest. 
    newNode->next = *dest; 
    //Now destination head points to newNode 
    *dest = newNode; 
    return; 
} 

Node *MergedSort(Node *a, Node *b){ 
    Node *dummy; // This slight change gave me segmentation fault. 
    Node *tail = dummy; 
    dummy->next = NULL; 

    while(1){ 
      if (a == NULL){ 
        tail->next = b; 
        break; 
      } 
      else if (b == NULL){ 
        tail->next = a; 
        break; 
      } 
      else if (a->data < b->data){ 
        MoveNode(&(tail->next), &a); 
      } 
      else{ 
        MoveNode(&(tail->next), &b); 
      } 
      tail = tail->next; 
    } 
    return (dummy->next); 
} 

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

Answer 1

dummy является структура. tail указывает на адрес этой структуры. Переменная структуры next указывает на NULL. Пока все хорошо.

Node dummy; 
Node *tail = &dummy; 
dummy.next = NULL; 

dummy является указатель на структуру. tail указывает на адрес этой структуры - ОК. Переменная структуры (разыменованная [1] - НЕ ОК) next незаконно доступна, потому что dummy еще не был инициализирован.

Node *dummy; // This slight change gave me segmentation fault. 
Node *tail = dummy; 
dummy->next = NULL; 

---

[1] dummy->next эквивалентно (*dummy).next

Answer 2

Проблема заключается в том, что когда вы делаете это

dummy->next = NULL; 

dummy еще не инициализирован. Выделение неинициализированного указателя - это неопределенное поведение.

Вам не нужно dummy вообще - просто назначить NULL для tail, переименовать его в head, и передать &head в MoveNode. Возвращение head завершить исправление:

Node *MergedSort(Node *a, Node *b) { 
    Node *head = NULL; 
    Node **tail = &head; 
    while(1) { 
     if (a == NULL){ 
      *tail = b; 
      break; 
     } else if (b == NULL){ 
      *tail = a; 
      break; 
     } else if (a->data < b->data){ 
      MoveNode(tail, &a); 
     } else{ 
      MoveNode(tail, &b); 
     } 
     tail = &((*tail)->next); 
    } 
    return head; 
} 

Demo.