c++ - 创建一个接受链表作为输入的合并排序

Question

这是我的一些代码

listnode *mergesort(struct listnode *list){
    struct listnode *L, *R, *head;
    int i = 0;
    head = list;
    while (list->next != NULL){
        if (i%2 == 0){              //it splits the linkedlist into 2 segments
                                    //it adds the elements in the linked list                                        
                                    // alternatively.
                                    //to a linked list R & L
            L=list->next;
            list->next = L->next;
            i=i+1;
        }
        else{
            R= list->next;
            list->next = R->next;
            i=i+1;
        }
        list = list->next;

    }
    MergeLists(mergesort(L),mergesort(R));
}

我不断收到段错误，无法弄清楚问题出在哪里。

Answer 1

首先，您的“计数”是在计数为偶数时向左 移动一个，而在计数为奇数时向右 移动一个。更不用说如果列表中只有一个项目，left 和 right 是未初始化的，循环的最后一行可能会导致您取消引用 null。

其次，您需要一些方法来标记 left 列表的末尾，否则您的合并排序将一遍又一遍地做同样的事情，直到溢出堆栈。

我们可以通过将左半部分的最后一个指针设置为 NULL 来做到这一点。请记住，MergeLists 必须修复所有这些问题才能再次创建一个漂亮的列表。

尝试这样的事情:

listnode *mergesort(listnode *list) {
  listnode *left = list, *right = list, *prev, *end = list;

  if (list == 0) { return list; }

  // move right once for every two we move end, so that we divide the middle
  while (end != 0) {
    end = end->next;
    prev = right; // keep track of the node before the start of right
    right = right->next;

    if (end != 0) {
      end = end->next;
    }
  }


  if (left->next == right) {
    // TODO swap items if necessary
    return left;
  }

  prev->next = 0; // split the list
  left = mergesort(left);
  right = mergesort(right);
  // TODO join left and right by calling MergeLists or whatever
  return left;
}

工作指针图:

prev->next = 0 removes -----|
                            v
list  -> [1] -> [2] -> [3] -> [4] -> [5] -> [6]
left  ----^                    ^
right -------------------------|