連結清單排序交換節點為什麼還得單獨交換next指針？

通過給連結清單排序，交換節點時，明明已經交換資料域，後面還得交換next指針：

typedef struct Node
{
  int id;    //資料域
  struct Node *next;  //指針域
}Node;

//連結清單節點排序
int NodeSort(Node *pHead)
{
  if (pHead == NULL)
  {
    return -1;
  }

  Node *pPre = NULL;
  Node *pCur = NULL; 
  Node tmp; //臨時交換變量
  
  //選擇法排序
  for (pPre = pHead->next; pPre != NULL; pPre = pPre->next)
  {
    for (pCur = pPre->next; pCur != NULL; pCur = pCur->next)
    {
      if (pPre->id > pCur->id) //升序
      {
        //交換資料域
        tmp = *pCur;
        *pCur = *pPre;
        *pPre = tmp;

        //交換next指針域（重要）
        tmp.next = pCur->next;
        pCur->next = pPre->next;
        pPre->next = tmp.next;

      }
    }
  }

  return 0;
}      

這是為什麼呢？下面給大家一步一步通過畫圖分析。

typedef struct Node
{
  int id;    //資料域
  struct Node *next;  //指針域
}Node;

Node *p1 = malloc( sizeof(Node) );
p1->id = 1;

Node *p2 = malloc( sizeof(Node) );
p2->id = 2;

p1->next = p2;
p2->next = NULL;      

我們将上面的代碼，畫一下記憶體四區圖（棧區、堆區、全局區、代碼區），由于這裡隻用到棧區和堆區，是以隻畫棧區和堆區的示例圖，這裡需要使用指針的一個規律：指針指向誰，就把誰的位址指派給指針。

很多時候，我們畫連結清單圖畫的都是簡潔圖：

下面通過畫圖說明一下連結清單節點交換，為什麼還得交換next指針？

Node tmp; //臨時交換節點
if (p1->id < p2->id) //降序
{
  //交換資料域
  tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;

  //交換指針域（重要）
  tmp.next = p1->next;
  p1->next = p2->next;
  p2->next = tmp.next;

}      

tmp = *p1;

将p1指向記憶體的值指派給tmp對應的記憶體中。

*p1 = *p2;

将p2指向記憶體的值分别指派給p1指向的記憶體。

*p2 = tmp;

将tmp記憶體的值指派給p2指向記憶體中。

這樣操作完後，發現p1的next指向NULL，p2的next指向p2本身，p1和p2兩個節點沒有關系。合理情況應該是，p1的next指向p2, p2的next指向NULL

是以，上面的交換，隻是把資料域成功交換了，next指針域并不符合我們要求。

下面開始重新交換next指針域：

tmp.next = p1->next;

p1->next = p2->next;

p2->next = tmp.next;