数据结构：链表常见的操作方法！！

        之前我们讲了单向有头链表的创建、插入（头插和尾插）、遍历、删除，除了这些操作方法，还有修改、查找（单个节点、中间节点、倒数第k个节点）、倒置、排序，此外也会讲到链表是否有环的判断方法。

typedef int DataType;

typedef struct node
{
DataType Data;
struct node *pNext;
}Node_t

一、修改

        先定义一个指针指向链表第一个有效节点；

        遍历查找要修改的节点，将旧的数据替换为新的数据。

关键代码示例：

Node_t *pTmpNode = NULL;
int Cnt = 0;

pTmpNode = pHead->pNext;
while (pTmpNode != NULL)
{
if (pTmpNode->Data == OldData)
{
pTmpNode->Data = NewData;
Cnt++;
}
pTmpNode = pTmpNode->pNext;
}

二、查找单个节点的地址

        定义一个指针，指向链表第一个有效节点；

        遍历，当指针指向的节点的值为我们要查找的值，返回该节点的地址。

关键代码示例：

Node_t *pTmpNode = NULL;

pTmpNode = pHead->pNext;
while (pTmpNode != NULL)
{
if (pTmpNode->Data == TmpData)
{
return pTmpNode;
}
pTmpNode = pTmpNode->pNext;
}

return NULL;

三、查找中间节点的地址

        定义两个指针，一个快指针，一个慢指针，都从链表第一个有效节点开始；

        遍历，让快指针走两步（先让快指针走一步后判断，若快指针指向了空，则直接返回慢指针的地址，若不为空则让快指针再走一步），慢指针走一步，当快指针走到NULL时，慢指针的地址即为中间节点的地址。

关键代码示例：

Node_t *pFast = NULL;
Node_t *pSlow = NULL;

pFast = pSlow = pHead->pNext;
while (pFast != NULL)
{
pFast = pFast->pNext;
if (NULL == pFast)
{
return pSlow;
}
pFast = pFast->pNext;
pSlow = pSlow->pNext;
}

四、查找倒数第k个节点地址

        定义两个指针，一个快指针，一个慢指针，都从头指针开始；  

        先让快指针走K步（当快指针不指向NULL时，for循环走k步，循环次数小于k步），若快指针指向了空，则直接返回空（说明没有倒数第k个节点），遍历让快指针和慢指针同时走，当快指针指向空时，慢指针的地址即为中间节点的地址。

关键代码示例：

Node_t *pFast = NULL;
Node_t *pSlow = NULL;
int i = 0;

pFast = pSlow = pHead;
for (i = 0; pFast != NULL && i < Nth; i++)
{
pFast = pFast->pNext;
}

if (NULL == pFast)
{
return NULL;
}

while (pFast != NULL)
{
pFast = pFast->pNext;
pSlow = pSlow->pNext;
}

return pSlow;

五、销毁

        定义两个指针ptmp和pfree，都先指向头指针；

        遍历让ptmp指向下一个，释放pfree的空间，再让pfree赋值为ptmp

        注意最后要将释放后的指针置空，避免野指针，即传入二级指针，将**pHead置空。

关键代码示例：

Node_t *pTmpNode = NULL;
Node_t *pFreeNode = NULL;

pTmpNode = *ppHead;
pFreeNode = *ppHead;
while (pTmpNode != NULL)
{
pTmpNode = pTmpNode->pNext;
free(pFreeNode);
pFreeNode = pTmpNode;
}
*ppHead = NULL;

return 0;

六、倒置

        定义两个指针ptmp和pinsert，都指向第一个有效节点；

        将头指针的pNext置空，也就是将头节点与第一个有效节点断开；

        遍历让ptmp向后走，用头插法插入pinsert。

关键代码示例：

Node_t *pTmpNode = NULL;
Node_t *pInsertNode = NULL;

pTmpNode = pInsertNode = pHead->pNext;
pHead->pNext = NULL;

while(pTmpNode != NULL)
{
pTmpNode = pTmpNode->pNext;
pInsertNode->pNext = pHead->pNext;
pHead->pNext = pInsertNode;
pInsertNode = pTmpNode;
}

return 0;

七、排序

1.冒泡排序

• 1. 边界检查

  • 先判断链表是否为空，或只有一个有效节点。

  • 如果是，直接返回，无需排序。

• 2. 初始化指针

  • pTmpNode1 和 pTmpNode2：用于遍历并比较相邻的两个节点。

  • pEnd：标记已排序区间的尾部，初始为 NULL，表示还没有任何节点完成排序。

  • TmpData：临时变量，用于交换节点的值。

• 3. 外层循环：控制排序轮次

  • 使用 while(1) 作为无限循环，通过内部条件判断来终止。

  • 每一轮结束后，最大的未排序值会被 “冒泡” 到当前未排序区间的末尾，因此 pEnd 会向前移动。

• 4. 内层循环：相邻节点比较与交换

  • 每轮开始时，重置 pTmpNode1 和 pTmpNode2 到链表的起始有效节点。

  • 只要 pTmpNode2 不等于 pEnd（即还没遍历到已排序区间），就持续比较：

    • 如果 pTmpNode1->Data > pTmpNode2->Data，则交换两者的值。

    • 然后将 pTmpNode1 和 pTmpNode2 同时向后移动一个节点。

• 5. 推进已排序区间

  • 当一轮内层循环结束后，当前未排序区间的最大值已经被移动到末尾。

  • 将 pEnd 更新为 pTmpNode1，表示该节点及其之后的部分已经有序。

• 6. 终止条件

  • 当 pEnd 等于 pTmpNode2 时，说明未排序区间只剩一个节点，链表已经完全有序，退出外层循环。

• 7. 结束返回

  • 排序完成后，函数返回 0。

关键代码示例：

Node_t *pTmpNode1 = NULL;
Node_t *pTmpNode2 = NULL;
Node_t *pEnd = NULL;
DataType TmpData;

if (NULL == pHead->pNext || NULL == pHead->pNext->pNext)
{
return 0;
}

while (1)
{
pTmpNode1 = pHead->pNext;
pTmpNode2 = pHead->pNext->pNext;

if (pEnd == pTmpNode2)
{
break;
}

while (pTmpNode2 != pEnd)
{
if (pTmpNode1->Data > pTmpNode2->Data)
{
TmpData = pTmpNode1->Data;
pTmpNode1->Data = pTmpNode2->Data;
pTmpNode2->Data = TmpData;
}

pTmpNode1 = pTmpNode1->pNext;
pTmpNode2 = pTmpNode2->pNext;
}
pEnd = pTmpNode1;
}

return 0;

2.选择排序        

• 1. 边界检查
  • 先判断链表是否为空，或只有一个有效节点。
  • 如果是，直接返回，无需排序。
• 2. 初始化排序指针
  • 定义 pSwapNode，指向当前待排序区间的起始节点，初始化为链表第一个有效节点。
  • 定义 pMinNode 用来记录当前区间的最小值节点。
  • 定义 pTmpNode 用来遍历当前区间寻找最小值。
• 3. 外层循环：确定待排序区间
  • 从 pSwapNode 开始，直到链表末尾（pSwapNode->pNext != NULL）。
  • 每次循环确定一个位置的最终值。
• 4. 内层循环：寻找最小值节点
  • 将 pMinNode 初始化为当前 pSwapNode。
  • 用 pTmpNode 从 pSwapNode->pNext 开始遍历剩余节点。
  • 比较每个节点的数据值，更新 pMinNode 指向值更小的节点。
• 5. 交换节点值
  • 如果找到的最小值节点 pMinNode 不是当前的 pSwapNode。
  • 交换两者的 Data 字段，把最小值放到当前 pSwapNode 的位置。
• 6. 推进排序区间
  • 将 pSwapNode 移动到下一个节点，进入下一轮排序。
  • 重复步骤 3–5，直到整个链表有序。
• 7. 结束返回
  • 排序完成后，函数返回 0。

关键代码示例：

Node_t *pSwapNode = NULL;
Node_t *pTmpNode = NULL;
Node_t *pMinNode = NULL;
DataType TmpData;

if (NULL == pHead->pNext || NULL == pHead->pNext->pNext)
{
return 0;
}

pSwapNode = pHead->pNext;

while (pSwapNode->pNext != NULL)
{
pMinNode = pSwapNode;
pTmpNode = pSwapNode->pNext;
while (pTmpNode != NULL)
{
if (pTmpNode->Data < pMinNode->Data)
{
pMinNode = pTmpNode;
}
pTmpNode = pTmpNode->pNext;
}
if (pSwapNode != pMinNode)
{
TmpData = pSwapNode->Data;
pSwapNode->Data = pMinNode->Data;
pMinNode->Data = TmpData;
}
pSwapNode = pSwapNode->pNext;
}

return 0;

八、判断链表是否有环（了解）