算法-链表之简单算法题
上一阶段的字符串系列之后很长时间都没有更新文章，现在接着来，本阶段是链表系列的，链表系列的算法题我不会再用大量篇幅写一个问题的解决方案，针对一个问题写一个解决方案，所以篇幅会小很多。这篇文章会介绍和链表相关的简单算法题，后面还会介绍复杂算法题。
- 添加/删除结点
- 从尾到头打印链表
- 翻转单链表
- 在O(1)时间内删除链表结点
1.添加/删除结点
我们都知道，链表的添加和删除操作相比数组是很方便的，因为链表不要求结点的物理顺序和逻辑顺序相同，所以添加删除结点的时候不需要像数组一样移动大量的结点，借助指针，修改指针指向，我们就可以很方便的实现添加和删除结点的操作。
添加/删除结点是链表类算法题中比较简单的操作了，不会有太大问题。主要是在注意细节，添加/删除的时候要注意判断链表是否为空，如果链表为空，就要修改头指针的指向，也就是修改头指针指向的地址。
代码
链表的数据结构的定义：
注意：这些声明中包含了一个自引用结构的列子。在定义结构ListNode之前，已经定义了指向该结构的指针。C语言允许定义指向尚不存在的类型的指针。
typedef struct ListNode *list_pointer;
typedef struct ListNode
{
int value;
list_pointer link;
};
list_pointer pHead;
在链表尾添加节点
有在前端，中间插入结点的，也有在尾部，这里的例子是在链表尾插入结点。注意，如果链表为空，那么添加结点需要修改头指针的指向，所以这里接收的参数是头指针的地址。
//pHead是指向指针的指针 ListNode** p
void addToTail(list_pointer *pHead, int value){
list_pointer node = (list_pointer)malloc(sizeof(ListNode));
if (node == NULL)
{
fprintf(stderr, "Faile\n");
exit(1);
}
node->value = value;
node->link = NULL;
if (*pHead == NULL)
{
*pHead = node;
}
else{
list_pointer p = *pHead;
while (p->link != NULL){
p = p->link;
}
p->link = node;
}
}
删除中间结点：
删除指定值的结点，我们不知道该结点在什么位置，所以需要遍历链表找到结点。
//如果删除首节点，那么需要改变首节点指针的指向
bool deleteNode(list_pointer *pHead, int value){
if (*pHead == NULL)
{
fprintf(stderr, "The linklist is empty!\n");
exit(1);
}
ListNode *node = NULL;
if ((*pHead)->value == value){//删除首节点
node = *pHead;
*pHead = (*pHead)->link;
free(node);
return true;
}
else{
list_pointer p = *pHead;
while (p->link != NULL && p->link->value != value){
p = p->link;
}
if (p->link != NULL && p->link->value == value)
{
node = p->link;
p->link = p->link->link;
free(node);
}
}
}
2.从尾到头打印链表
看到这到道题的第一反应是从头到尾打印链表会比较简单，所以我们可以改变链表的指针指向，但是这样会改变链表原来的结构，是否允许改变链表的结构，这个取决于面试官。这里的例子是不改变链表结构。
算法思想
从尾到头打印链表也就是说先存入的元素后输出，后存入的先输出，和栈“后进先出”的思想一样，所以我们可以在遍历链表的时候先将元素存入栈中，再循环遍历栈输出元素。
想到了使用栈，而递归的本质就是使用栈存储，那么我们使用递归也能实现同样的效果，下面的例子就是用递归实现的。
代码：
void PrintListReversingly(list_pointer pHead) {
list_pointer p = pHead;
if (p) {
if (p->link) {
PrintListReversingly(p->link);
}
printf("链表元素：%d\n", p->value);
}
}
使用递归代码会简洁很多，但是当链表非常长的时候，函数调用的层级会很深，可能会导致函数调用栈溢出，显式的使用栈基于循环来遍历的鲁棒性会好一些。
3.翻转单链表
题目：写一个函数，输入链表的头结点，翻转该链表，并返回翻转后的链表的头结点。
算法思想
翻转链表
看上面的图，如果是对结点i翻转链表，就是改变i的link的指向，将它指向前一个结点h，但是这样会导致i指向j的链丢失，所以我们需要存储下这个值，也就是说，在一次改变指针指向的操作中，我们需要存储下前一个结点h，后一个结点j，和当前结点i。此外，我们还需要明确，在翻转了链表之后，原来的头结点变成了尾结点，而现在的尾节点呢，就是NULL。分析完这些之后很容易写出代码。
代码
//翻转链表
list_pointer Invert(list_pointer pHead)
{
list_pointer middle, trail;
middle = NULL;
//当pHead指向原链表的最后一个结点的link时，退出循环
//此时middle刚好指向原链表的最后一个结点
while (pHead) {
trail = middle;
middle = pHead;//此时middle和pHead指向的地址相同
pHead = pHead->link;
middle->link = trail;
}
return middle;
}
4.在O(1)时间内删除链表结点
常规的思维，删除链表结点需要知道它的前一个结点，简单的三句代码，就是判断p->link->value == value，然后修改p->link = p->link->link，释放p->link.这样就需要遍历链表，知道要删除的结点的前一个，时间复杂度为O(n)。如果换一种思路呢？
算法思想
假设结点h,i,j是链表中相邻的3个结点，现在要删除i，可以进行下面3步：
- 将结点j的值复制到结点i上；
- 修改i的link；
- 释放结点j。
现在需要考虑一下特殊情况下是否也满足。当删除的节点是头结点时，需要修改头结点的link指针。当删除的是尾结点时，它没有下一个结点，所以需要遍历链表，得到它的前一个结点。当链表只有一个结点时，删除的结点是头结点（尾节点），需要将头指针的指向置为NULL。
代码
//在O(1)内删除一个结点
void DeleteNode(list_pointer *pHead, ListNode *node)
{
if (!(*pHead) || !node)
return;
//要删除的不是尾结点
if (node->link)
{
ListNode *pNext = node->link;
node->value = pNext->value;
node->link = pNext->link;
free(pNext);
}
//链表中只有一个结点删除头结点，也是尾结点
else if (*pHead == node)//node->link为NULL
{
free(node);
*pHead = NULL;
}
else//链表中有多个结点，删除的是尾结点
{
list_pointer p = *pHead;
while (p->link != node)
{
p = p->link;
}
p->link = NULL;
free(node);
}
}
总结
这些题难度都不大，使用指针很灵活，但是也很容易出错，主要是关注细节。这篇就到这里了，不足之处，还请多指教~
