【数据结构】单链表中，如何实现 将链表中所有结点的链接方向“原地”逆转

一.实现一个单链表（无头单向不循环）

我们首先实现一个无头单向不循环单链表。

写出基本的增删查改功能，以及其它的一些功能（可忽略）。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;SLTNode* BuyListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){printf("malloc failed.\n");exit(-1);}newnode->data = x;newnode->next = NULL;
}void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找到尾结点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SListPopBack(SLTNode** pphead)
{assert(*pphead != NULL);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}void SListPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{SLTNode* newnode = BuyListNode(x);if (*pphead == pos){newnode->next = *pphead;*pphead = newnode;}else{SLTNode* posPrev = *pphead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newnode;newnode->next = pos;}
}void SListErase(SLTNode** pphead, SLTNode* pos)
{if (*pphead == pos){*pphead = pos->next;free(pos);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}void SListDestroy(SLTNode** pphead)
{assert(*pphead);SLTNode* cur = *pphead;SLTNode* next = (*pphead)->next;while (next){free(cur);cur = next;next = next->next;}free(cur);*pphead = NULL;
}//通过一趟遍历确定长度为n的单链表中值最大的结点
SLTNode* SListFindMax(SLTNode* pphead)
{assert(pphead);SLTNode* cur = pphead;SLTNode* maxnode = pphead;SLTDataType max = pphead->data;while (cur){if (cur->data > max){max = cur->data;maxnode = cur;}cur = cur->next;}return maxnode;
}

二.原地逆转

接下来我们要写一个接口，实现：将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求空间复杂度为O（1）

那么，我们需要将链表遍历，进行逆转，改变链接方向 时，要尤其注意，避免行差踏错。

//将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求空间复杂度为O（1）
void SListReverse(SLTNode** pphead) 
{SLTNode* head = *pphead;   //此指针在每次循环中始终指向当前链表的头SLTNode* tmp = head->next; //此指针在每次循环中始终指向要被后删头插的节点SLTNode* oldhead = *pphead;   //此指针在每次循环中始终指向原本的头结点，不会改变指向while (tmp) //如果tmp为空，则代表逆序结束，旧头的next已经是空的了，成为新链表的末尾{oldhead->next = tmp->next; //将tmp架空，实际是后删操作的一部分tmp->next = head; //让tmp变成新的头，实际是头插操作的一部分 head = tmp; //换头tmp = oldhead->next; //让tmp变成下次循环中待删除的节点}*pphead = head;
}

或许仅仅一段代码不足以让你理解，我们可以来看下面的图。

对照着代码，每一次循环就是下面的一行。

最后一行即为逆转后的链表。

 

 三.测试运行

最后，我们来看一下上面代码的运行效果。

我们可以写一个测试函数。

void TestSList()
{SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPushBack(&plist, 5);SListPrint(plist);SListReverse(&plist);SListPrint(plist);SListDestroy(&plist);}int main()
{TestSList();return 0;
}

运行结果

这样，我们就实现了链表的原地逆转。