通過對實際節點進行排序來排序鏈接列表，而不僅僅是通過交換節點值

Question

我想對鏈接列表排序，以便節點按排序順序排列。我查了幾個算法，但它們都交換數據值而不是實際節點本身。有誰知道我在哪裏可以找到一些關於如何交換節點本身的代碼，而不僅僅是值？

Answer 1

這是合併排序鏈接列表的傳統和最快的方式。這是一種自下而上的樣式合併排序，它使用指向節點的指針數組來保存中間列表，其中array [i]爲空或指向列表中的2，並且指向功耗i節點。原始列表中的節點將合併到數組中，然後將數組中的列表合併爲一個排序列表。 HP/Microsoft C++ STL std :: list :: sort使用相同的算法。

/* prototype */ 
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2); 

/* sort list using array of pointers to first nodes of list */ 
/* aList[i] = NULL or ptr to list with 2 to the power i nodes */ 

#define NUMLISTS 32     /* size of array */ 
NODE * SortList(NODE *pList) 
{ 
NODE * aList[NUMLISTS];    /* array of lists */ 
NODE * pNode; 
NODE * pNext; 
int i; 
    if(pList == NULL)    /* check for empty list */ 
     return NULL; 
    for(i = 0; i < NUMLISTS; i++) /* zero array */ 
     aList[i] = NULL; 
    pNode = pList;     /* merge nodes into array */ 
    while(pNode != NULL){ 
     pNext = pNode->next; 
     pNode->next = NULL; 
     for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){ 
      pNode = MergeLists(aList[i], pNode); 
      aList[i] = NULL; 
     } 
     if(i == NUMLISTS)   /* don't go past end of array */ 
      i--; 
     aList[i] = pNode; 
     pNode = pNext; 
    } 
    pNode = NULL;     /* merge array into one list */ 
    for(i = 0; i < NUMLISTS; i++) 
     pNode = MergeLists(aList[i], pNode); 
    return pNode; 
} 

/* mergelists - compare uses src2 < src1   */ 
/* instead of src1 <= src2 to be similar to C++ STL */ 

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2) 
{ 
NODE *pDst = NULL;     /* destination head ptr */ 
NODE **ppDst = &pDst;    /* ptr to head or prev->next */ 
    if(pSrc1 == NULL) 
     return pSrc2; 
    if(pSrc2 == NULL) 
     return pSrc1; 
    while(1){ 
     if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */ 
      *ppDst = pSrc2; 
      pSrc2 = *(ppDst = &(pSrc2->next)); 
      if(pSrc2 == NULL){ 
       *ppDst = pSrc1; 
       break; 
      } 
     } else {      /* src1 <= src2 */ 
      *ppDst = pSrc1; 
      pSrc1 = *(ppDst = &(pSrc1->next)); 
      if(pSrc1 == NULL){ 
       *ppDst = pSrc2; 
       break; 
      } 
     } 
    } 
    return pDst; 
} 

Answer 2

請參閱本： http://www.geeksforgeeks.org/merge-sort-for-linked-list/

它顯示瞭如何鏈表使用合併排序而那也是通過改變指針進行排序。

Answer 3

不是交換內容，而是將指針/「next_item」變量指向新訂單的正確節點。