合并两个排序的循环单链表

Question

我在C语言课程考试前练习一些算法问题，我被这个问题卡住了（至少3个小时甚至4个小时），我不知道如何回答：

您有两个已排序的循环单链接列表，必须合并它们并返回新循环链接列表的标题，而不创建任何新的额外节点。返回的列表也应该进行排序。

节点结构为：

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

我尝试了很多方法（递归和非递归），但都没有解决问题。

谢谢你的帮助。

Answer 1

合并两个已排序列表的示例代码。要检查循环列表的结束节点，请检查指向列表头节点的指针，而不是NULL，到达一个列表的末尾后，您需要从另一个列表中一次链接其余节点，因为终止符不是NULL。合并后，您需要将最后一个节点的下一个指针设置为头节点，使其成为循环列表。代码检查Src2

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    while(1){
        if(pSrc1 == NULL){              /* if end of Src1 */
            *ppDst = pSrc2;             /*   append remainder of Src2 */
            break;                      /*   and break out of loop */
        }
        if(pSrc2 == NULL){              /* if end of Src2 */
            *ppDst = pSrc1;             /*   append remainder of Src1 */
            break;                      /*   and break out of loop */
        }
        if(pSrc2->data < pSrc1->data){  /* if Src2 < Src1 */
            *ppDst = pSrc2;             /*   append node from Src2 */
            pSrc2 = *(ppDst = &(pSrc2->next));
            continue;
        } else {                        /* else Src1 <= Src2 */
            *ppDst = pSrc1;             /*   append node from Src1 */
            pSrc1 = *(ppDst = &(pSrc1->next));
            continue;
        }
    }
    return pDst;
}

Answer 2

首先维护一个有两个链表的队列。以下是它的伪代码：-

 queue* merge_queues (queue* first, queue* second)
       {

           queue* merged_queue = create_queue(first->capacity + second->capacity);
           if (first != NULL && second != NULL){
              while ( !is_empty (first) && !is_empty (second)){
           int max;
           if ( peekqueue (first) > peekqueue (second)){
               max = peekqueue (first);
               dequeue (first);
           }
           else{
                max = peekqueue (second);
                dequeue (second);
           }
           enqueue( merged_queue, max);
        }
         while ( !is_empty (first)){
              enqueue( merged_queue, peekqueue(first));
              dequeue (first);
         }
         while (!is_empty (second)){
             enqueue (merged_queue, peekqueue(second));
             dequeue (second);
        }
    }
    return merged_queue;
}

Answer 3

这基本上是合并排序的合并步骤。

在链表中，可以就地完成。

其思想是为每个列表使用一个迭代器，并且在合并列表中的数据用尽之前，将list1中的节点与list2中的节点进行比较（如果list2使用迭代器）

通过维护额外的prev迭代器，在当前节点之前插入节点。

请注意，在该算法的整个过程中，没有创建任何新节点，您所做的只是将节点从list2移动到list1。

复杂度，如果此过程是O（n）。