链表排序交换节点为什么还得单独交换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;