算法-链表之复杂算法题
好多天没有更新文章，今天更新的是链表的复杂算法题，这一篇完了之后，链表相关的也结束了，会进入下一个环节。
- 圆圈中最后剩下的数字
- 复杂链表的复制
- 二叉排序树转换成双向链表
1. 圆圈中最后剩下的数字
问题描述：0,1,2,...,n-2,n-1这n个数字排成一个圆圈，从数字0开始，每次删除圆圈中的第m个数字。求出圆圈中最后剩下的 一个数字。如图：
由0~4五个数字组成的圆环
每次删除第3个数字，删除顺序依次是2，0，4，1，最后剩下的数字是3。
算法思想
思路一：用链表模拟数字排成圆圈的数据结构，就是一个环形链表。从链表的头结点开始，每删除一个结点需要m步运算（从链表的第一个结点开始遍历），链表中一共有n个结点，时间复杂度为O(mn)。这一种思想的实现要简单一些，也比较耗时一些。
思路二：第二种思路主要是找到每次删除的规律，更像一种数学归纳。首先定义以下概念：
f(n,m): 表示在n个围成圈的数字中每次删除第m个数字之后，最后剩下的数字。很显然，第一次删除的数字是(m-1)%n,记作k。
f '(n-1,m): 表示第一次删除第m个几点之后，在剩下的n-1个数字中，每次删除第k个数字的最后剩下的数字。为什么要用不同的函数表示呢？因为第一次删除k之后，剩下的数字序列为k+1,k+2,...,n-2,n-1,0,1,...,k-1，数字不再是从0开始了。
p(x)=x-k-1: 是删除第一个数字之后，剩下的n-1个数字序列k+1,k+2,...,n-1,0,1,...,k-1在0,1,...,n-2序列上的映射关系。p(x)=x-k-1表示映射前是x,映射后是x-k-1。如下，
p(x)的表示的映射关系
p'(x)=x+k+1: 是p(x)的逆映射，表示银蛇之后的x,那么映射前是x+k+1。
基于上面的定义，我们首先可以得到这样的关系f(n,m)=f'(n-1,m),最初序列最后剩下的数字一定是删除一个数字之后的序列最后剩下的数字。综上，可以得到这样的关系f'(n-1,m)=p'(f(n-1,m))=[f(n-1,m)+k+1]%n，把k=(m-1)%n带入上式，得f(n,m)=f'(n-1,m)=[f(n-1,m)+m]%n，得到递归公式。在从0开始的序列中，每次删除第m个，下一次还是从0开始的序列，所以最后剩下的数字一定是0.
递归公式
两种方法相比，第一种思路更好理解，第二种思路更创新，通过找到规律来解题，但是分析要困难一些。
代码
第一种思路的代码。
1.先定义数据结构
typedef struct ListNode *list_pointer;
typedef struct ListNode
{
int value;
list_pointer link;
};
list_pointer pHead;
2.构造循环链表，每次删除链表中的第m个结点。
//使用链表
int LastRemainingInList(unsigned int n, unsigned int m)
{
if (n < 1 || m < 1)
return -1;
list_pointer pHead=NULL, node=NULL, pre=NULL, temp=NULL;
for (int i = 0; i < n; i++)
{
if (i == 0)
{
pHead = (list_pointer)malloc(sizeof(ListNode));
pHead->value = 0;
pHead->link = NULL;
pre = pHead;
continue;
}
node = (list_pointer)malloc(sizeof(ListNode));
node->value = i;
node->link = NULL;
pre->link = node;
pre = node;
}
//printList(pHead);
node->link = pHead;//环形链表
node = pHead;
for (int i = 1; i < n ; i++)//循环n-1次，最后链表中剩下的就是最终结果了
{
for (int j = 1; j < m;j++)//向前走m-1步
{
pre = node;
node = node->link;
}
temp = node;
pre->link = node->link;
node = node->link;
free(temp);
}
printf("LastRemainingInList：%d ", node->value);
return node->value;
}
第二种思路的代码，可以看到，分析很难，但是代码很简单
int LastRemaining(unsigned int n, unsigned int m)
{
if (n < 1 || m < 1)
return -1;
int last = 0;
for (int i = 2; i <= n; i++)//剩下的n-1个数字
{
last = (last + m) % i;
}
printf("LastRemaining：%d ", last);
return last;
}
2. 复杂链表的复制
问题：有这样一个复杂链表，每个结点除了pNext这个指向下一个结点的指针外，还有pSibling这个指向链表中任意结点或者NULL的指针。完成这样一个复杂链表的复制。
复杂链表
数据结构定义如下：
//复杂链表数据结构
typedef struct ComplexListNode *ComplexListPointer
typedef struct ComplexListNode
{
int value;
ComplexListPointer pNext;
ComplexListPointer pSibling;
};
ComplexListPointer pHead;
算法思想
常规思路：这样的链表，可以将复制分为两步，第一步是复制链表上的所有结点，使用pNext连接起来，第二步是复制pSibling指针。在复制pSibling的时候，需要注意，这里会有一个O(n)的遍历。假设原链表中一个结点的pSibling指向的结点是s,我们不知道s在原链表中是哪个结点，需要遍历原链表找到s,才能完成复制。每个结点的pSibling指针的复制都需要O(n)的遍历，整个算法的时间复杂度为O(n^2).
思路二：对常规思路的优化。上一种方法的时间花费主要是在定位pSibling上，如果能减少定位用的时间，效率也会变高。我们可以使用hash表来优化。第一步还是先复制链表上的所有结点，用pNext连接，假设原始链表上的结点N复制之后的结点是N'，使用hash表保存<N,N'>的对应关系。第二步还是设置链表中每个结点的pSibling。原始链表中结点N的pSibling指向的结点S，那么复制之后的结点N'的pSibling指向的就是S'，由于有hash表，我们可以在O(1)时间内根据S找到S'.这里是使用空间换时间，需要O(n)的辅助存储空间。
思路三：不需要额外的存储空间能不能完成这个题目呢？这就是思路三了。第一步，复制每个结点，并把复制的结点接在原始结点的后面。如图，
复制之后的结点插入到原结点后面
第二步，设置结点的pSibling指针，因为复制之后的结点N'在原始结点N的下一个，那么结点N的pSibling是S，对应的复制之后的结点S'就是S->pNext。如图，
设置pSibling指针
第三步，将原链表和复制之后的链表分离。
代码
这里贴的是第三种思路的代码。我们可以将每一步定义为一个函数，分步骤解决问题。
1.复制结点，插入到原结点后面。
//复制链表中的结点
void CloneNodes(ComplexListPointer pHead)
{
ComplexListNode *pNode = pHead;
while(pNode != NULL)
{
ComplexListPointer pCloned = (ComplexListPointer)macoll(ComplexListNode);
pCloned->value = pNode->value;
pCloned->pNext = pNode->pNext;
pCloned->pSibling = NULL;//暂时不设置pSibling
pNode->pNext = pCloned;//将complexNode插入到原链表中
pNode = pCloned->pNext;
}
}
2.设置pSibling指针。
//设置pSibling指针
void ConnectSiblingNodes(ComplexListPointer pHead)
{
ComplexListNode *pNode = pHead;
while(pNode != NULL)
{
//找到复制之后的结点
ComplexListPointer pCloned = pNode->pNext;
if(pNode->pSibling != NULL)//不为空
{
pCloned->pSibling = pNode->pSibling->pNext;
}
//指向下一个原始结点
pNode = pCloned->pNext;
}
}
3.拆分链表
//拆分两个链表
ComplexListPointer ReconnectNodes(ComplexListPointer pHead)
{
ComplexListPointer pNode = pHead;
ComplexListPointer pClonedHead = NULL;
ComplexListPointer pClonedNode = NULL;
if(pNode != NULL)
{
pClonedHead = pClonedNode = pNode->pNext;
pNode->pNext = pClonedNode->pNext;
pNode = pNode->pNext;
}
while(pNode != NULL)
{
//pNode永远指向pClonedNode的后一个结点
pClonedNode->pNext = pNode->pNext;
pClonedNode = pClonedNode->pNext;
pNode->pNext = pClonedNode->pNext;
pNode = pNode->pNext;
}
return pClonedHead;
}
4.合并函数
ComplexListPointer Clone(ComplexListPointer pHead)
{
CloneNodes(pHead);
ConnectSiblingNodes(pHead);
return ReconnectNodes(pHead);
}
3.二叉排序树转换成双向链表
问题：将一棵二叉搜索树转换成有序的双向链表。不允许使用额外的存储空间，只能通过移动指针实现。
二叉搜索树转换成双向链表
算法思想
首先，可以看出二叉树和双向链表的结构很类似，二叉树的每个结点有左，右两个指针，对应到双向链表中，左指针就是链表结点指向前一个结点的指针，右指针就是指向后一个结点的指针。接下来，分析二叉搜索树的特点，二叉搜索树是排好序的，左结点比根节点小，右结点比根节点大。对该树进行中序遍历，就是排好序的了。先对左子树进行遍历，遍历到的最后一个结点就是左边子树最大的结点，然后将这个结点接到根结点，再遍历右边子树，和遍历左子树类似。
** 二叉树的遍历，一般采用递归实现**，所以，这里我们使用递归。
代码
1.定义二叉搜索树的数据结构
//二叉搜索树定义
typedef struct BinaryTreeNode *NodePointer;
typedef struct BinaryTreeNode
{
int value;
NodePointer left;
NodePointer right;
};
NodePointer root;
2.转换
//转换
BinaryTreeNode* Convert(BinaryTreeNode *root)
{
BinaryTreeNode *pLastNodeInList;//标记现有链表中的最后一个结点
if (root != NULL)
{
//每次新遍历到一个结点都要改变LastNodeInList指针的指向
//需要传入地址
ConvertNode(root, &pLastNodeInList);
}
//转换结束，但是不知道链表的头结点
//根据链表的LastNodeInList向前遍历，找到头结点
BinaryTreeNode *pHead = pLastNodeInList;
//left指向链表中的前一个结点
while(pHead != NULL && pHead->left !=NULL)
pHead = pHead->left;
return pHead;
}
//转换结点
/*
node:当前要遍历的结点；
pLastNodeInList:上一次转换之后的链表中的最后一个结点，也是当前链表中最大的结点。
*/
void ConvertNode(BinaryTreeNode *node, BinaryTreeNode **pLastNodeInList)
{
if(node == NULL)
return;
BinaryTreeNode *pCurrent = node;
//中序遍历左子树
if(pCurrent->left != NULL)
ConvertNode(pCurrent->left, pLastNodeInList);
//处理根节点
pCurrent->left = *pLastNodeInList;
//设置链表中上一个结点的右指针
if(*pLastNodeInList != NULL)
(*pLastNodeInList)->right = pCurrent;
*pLastNodeInList = pCurrent;
//中序遍历右子树
if(pCurrent->right != NULL)
ConvertNode(pCurrent->right, pLastNodeInList);
}
总结
链表系列到这里就结束了，复杂链表列有3道题，和简单题相比，分析要更多一些，从中我们可以看到，链表相关的题，怎么变都在围绕指针，所以基本的增加，删除结点，遍历都要很熟悉，再结合存储结构的特点，单向链表，双向链表，二叉树，一层层分析优化就可以找到解决方法。这也是我最近复习的成果，欢迎指教~
