c -为什么在SortedMerge()中用**s替换*s会导致程序崩溃

Question

在调试时我发现用*s替换**s使程序正常工作，但我不明白为什么**s在SortedMerge()函数中导致错误，请帮助

#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
    int data;
    struct node* next;
};
/* function prototypes */
struct node* SortedMerge(struct node* a, struct node* b);
void FrontBackSplit(struct node* source,
          struct node** frontRef, struct node** backRef);
/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct node **head)
{
    /*if list empty or contains one element, return head*/
    if((*head==NULL)||((*head)->next)==NULL)
        return *head;
    /*if control here, implies, atleast 2 nodes present in ll*/
    struct node* a=NULL;
    struct node* b=NULL;
    FrontBackSplit(*head,&a,&b);
    MergeSort(&a);
    MergeSort(&b);
    *head=SortedMerge(a,b);
}
/* See http://geeksforgeeks.org/?p=3622 for details of this
   function */
struct node* SortedMerge(struct node* first,struct node* second)
{
    if((first==NULL)&&(second==NULL))
        return NULL;
    if(first==NULL)
        return (second);
    if(second==NULL)
    {
        return (first);
    }
    /*first and second list both have elements*/
    struct node **s=NULL;
    struct node *z=NULL;
    while((first!=NULL)&&(second!=NULL))
    {
        if(*s==NULL)
        {
            *s = malloc(sizeof(struct node));
            z = *s;
        }
        else
        {
            z->next = malloc(sizeof(struct node));
            z = z->next;
        }
        if(first->data<=second->data)
        {
            z->data = first->data;
            first = first->next;
        }
        else
        {
            z->data = second ->data;
            second = second ->next;
        }
    }
    while(first!=NULL)
    {
            z->next = malloc(sizeof(struct node));
            z = z->next;
            z->data = first->data;
            first = first->next;
    }
    while(second!=NULL)
    {
            z->next = malloc(sizeof(struct node));
            z = z->next;
            z->data = second->data;
            second = second->next;
    }
    z->next=NULL;
    return *s;
}
/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back halves,
     and return the two lists using the reference parameters.
     If the length is odd, the extra node should go in the front list.
     Uses the fast/slow pointer strategy.  */
void FrontBackSplit(struct node* head,struct node **first,struct node **last)
{
    struct node *slow_ptr=head;
    struct node *fast_ptr=head->next;
    if((head==NULL)||(head->next==NULL))
    {
        *first=head;
        *last=NULL;
        return;
    }
    while((fast_ptr!=NULL)&&(fast_ptr->next!=NULL))
    {
        fast_ptr=fast_ptr->next->next;
        slow_ptr=slow_ptr->next;
    }
    *last=slow_ptr->next;
    slow_ptr->next=NULL;
    *first=head;
    return;
}
/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back halves,
     and return the two lists using the reference parameters.
     If the length is odd, the extra node should go in the front list.
     Uses the fast/slow pointer strategy.  */

/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
  while(node!=NULL)
  {
   printf("%d ", node->data);
   node = node->next;
  }
}
/* Function to insert a node at the beginging of the linked list */
void push(struct node** head_ref, int new_data)
{
  /* allocate node */
  struct node* new_node =
            (struct node*) malloc(sizeof(struct node));
  /* put in the data  */
  new_node->data  = new_data;
  /* link the old list off the new node */
  new_node->next = (*head_ref);
  /* move the head to point to the new node */
  (*head_ref)    = new_node;
}
/* Drier program to test above functions*/
int main()
{
  /* Start with the empty list */
  struct node* res = NULL;
  struct node* a = NULL;
  /* Let us create a unsorted linked lists to test the functions
   Created lists shall be a: 2->3->20->5->10->15 */
  push(&a, 15);
  push(&a, 10);
  push(&a, 5);
  push(&a, 20);
  push(&a, 3);
  push(&a, 2);
  /* Sort the above created Linked List */
  MergeSort(&a);
  printf("n Sorted Linked List is: n");
  printList(a);
  getchar();
  return 0;
}

这里是SortedMerge()函数，我替换了…

struct node* SortedMerge(struct node* a, struct node* b)
{
  struct node* result = NULL;
  /* Base cases */
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);
  /* Pick either a or b, and recur */
  if (a->data <= b->data)
  {
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else
  {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}

Answer 1

split函数将列表分成两部分;没有分配或释放内存。(实际上*head == *a之后，但这并不重要)。

merge函数应该是split的逆:将两个块组合成一个列表，不分配或释放。但是它包含malloc语句。这一定是个错误;您应该通过调整哪个元素指向下一个元素来合并两个列表。

改变你的接口可能更简单:只要有split(struct node **a, struct node **b)，有预req *b = NULL，它将a的一半节点移动到b;然后是merge(struct node **a, struct node **b);，将b的所有节点移动到a。