好多天沒有更新文章，今天更新的是鏈表的復(fù)雜算法題，這一篇完了之后，鏈表相關(guān)的也結(jié)束了，會進入下一個環(huán)節(jié)。
- 圓圈中最后剩下的數(shù)字
- 復(fù)雜鏈表的復(fù)制
- 二叉排序樹轉(zhuǎn)換成雙向鏈表
1. 圓圈中最后剩下的數(shù)字
問題描述：0,1,2,...,n-2,n-1這n個數(shù)字排成一個圓圈，從數(shù)字0開始，每次刪除圓圈中的第m個數(shù)字。求出圓圈中最后剩下的 一個數(shù)字。如圖：
每次刪除第3個數(shù)字，刪除順序依次是2，0，4，1，最后剩下的數(shù)字是3。
算法思想
思路一：用鏈表模擬數(shù)字排成圓圈的數(shù)據(jù)結(jié)構(gòu)，就是一個環(huán)形鏈表。從鏈表的頭結(jié)點開始，每刪除一個結(jié)點需要m步運算（從鏈表的第一個結(jié)點開始遍歷），鏈表中一共有n個結(jié)點，時間復(fù)雜度為O(mn)。這一種思想的實現(xiàn)要簡單一些，也比較耗時一些。
思路二：第二種思路主要是找到每次刪除的規(guī)律，更像一種數(shù)學(xué)歸納。首先定義以下概念：
f(n,m): 表示在n個圍成圈的數(shù)字中每次刪除第m個數(shù)字之后，最后剩下的數(shù)字。很顯然，第一次刪除的數(shù)字是(m-1)%n,記作k。
f '(n-1,m): 表示第一次刪除第m個幾點之后，在剩下的n-1個數(shù)字中，每次刪除第k個數(shù)字的最后剩下的數(shù)字。為什么要用不同的函數(shù)表示呢？因為第一次刪除k之后，剩下的數(shù)字序列為k+1,k+2,...,n-2,n-1,0,1,...,k-1，數(shù)字不再是從0開始了。
p(x)=x-k-1: 是刪除第一個數(shù)字之后，剩下的n-1個數(shù)字序列k+1,k+2,...,n-1,0,1,...,k-1在0,1,...,n-2序列上的映射關(guān)系。p(x)=x-k-1表示映射前是x,映射后是x-k-1。如下，
p'(x)=x+k+1: 是p(x)的逆映射，表示銀蛇之后的x,那么映射前是x+k+1。
基于上面的定義，我們首先可以得到這樣的關(guān)系f(n,m)=f'(n-1,m),最初序列最后剩下的數(shù)字一定是刪除一個數(shù)字之后的序列最后剩下的數(shù)字。綜上，可以得到這樣的關(guān)系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開始的序列，所以最后剩下的數(shù)字一定是0.
兩種方法相比，第一種思路更好理解，第二種思路更創(chuàng)新，通過找到規(guī)律來解題，但是分析要困難一些。
代碼
第一種思路的代碼。
1.先定義數(shù)據(jù)結(jié)構(gòu)
typedef struct ListNode *list_pointer;
typedef struct ListNode
{
int value;
list_pointer link;
};
list_pointer pHead;
2.構(gòu)造循環(huán)鏈表，每次刪除鏈表中的第m個結(jié)點。
//使用鏈表
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;//環(huán)形鏈表
node = pHead;
for (int i = 1; i < n ; i++)//循環(huán)n-1次，最后鏈表中剩下的就是最終結(jié)果了
{
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個數(shù)字
{
last = (last + m) % i;
}
printf("LastRemaining：%d ", last);
return last;
}
2. 復(fù)雜鏈表的復(fù)制
問題：有這樣一個復(fù)雜鏈表，每個結(jié)點除了pNext這個指向下一個結(jié)點的指針外，還有pSibling這個指向鏈表中任意結(jié)點或者NULL的指針。完成這樣一個復(fù)雜鏈表的復(fù)制。
數(shù)據(jù)結(jié)構(gòu)定義如下：
//復(fù)雜鏈表數(shù)據(jù)結(jié)構(gòu)
typedef struct ComplexListNode *ComplexListPointer
typedef struct ComplexListNode
{
int value;
ComplexListPointer pNext;
ComplexListPointer pSibling;
};
ComplexListPointer pHead;
算法思想
常規(guī)思路：這樣的鏈表，可以將復(fù)制分為兩步，第一步是復(fù)制鏈表上的所有結(jié)點，使用pNext連接起來，第二步是復(fù)制pSibling指針。在復(fù)制pSibling的時候，需要注意，這里會有一個O(n)的遍歷。假設(shè)原鏈表中一個結(jié)點的pSibling指向的結(jié)點是s,我們不知道s在原鏈表中是哪個結(jié)點，需要遍歷原鏈表找到s,才能完成復(fù)制。每個結(jié)點的pSibling指針的復(fù)制都需要O(n)的遍歷，整個算法的時間復(fù)雜度為O(n^2).
思路二：對常規(guī)思路的優(yōu)化。上一種方法的時間花費主要是在定位pSibling上，如果能減少定位用的時間，效率也會變高。我們可以使用hash表來優(yōu)化。第一步還是先復(fù)制鏈表上的所有結(jié)點，用pNext連接，假設(shè)原始鏈表上的結(jié)點N復(fù)制之后的結(jié)點是N'，使用hash表保存<N,N'>的對應(yīng)關(guān)系。第二步還是設(shè)置鏈表中每個結(jié)點的pSibling。原始鏈表中結(jié)點N的pSibling指向的結(jié)點S，那么復(fù)制之后的結(jié)點N'的pSibling指向的就是S'，由于有hash表，我們可以在O(1)時間內(nèi)根據(jù)S找到S'.這里是使用空間換時間，需要O(n)的輔助存儲空間。
思路三：不需要額外的存儲空間能不能完成這個題目呢？這就是思路三了。第一步，復(fù)制每個結(jié)點，并把復(fù)制的結(jié)點接在原始結(jié)點的后面。如圖，
第二步，設(shè)置結(jié)點的pSibling指針，因為復(fù)制之后的結(jié)點N'在原始結(jié)點N的下一個，那么結(jié)點N的pSibling是S，對應(yīng)的復(fù)制之后的結(jié)點S'就是S->pNext。如圖，
第三步，將原鏈表和復(fù)制之后的鏈表分離。
代碼
這里貼的是第三種思路的代碼。我們可以將每一步定義為一個函數(shù)，分步驟解決問題。
1.復(fù)制結(jié)點，插入到原結(jié)點后面。
//復(fù)制鏈表中的結(jié)點
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;//暫時不設(shè)置pSibling
pNode->pNext = pCloned;//將complexNode插入到原鏈表中
pNode = pCloned->pNext;
}
}
2.設(shè)置pSibling指針。
//設(shè)置pSibling指針
void ConnectSiblingNodes(ComplexListPointer pHead)
{
ComplexListNode *pNode = pHead;
while(pNode != NULL)
{
//找到復(fù)制之后的結(jié)點
ComplexListPointer pCloned = pNode->pNext;
if(pNode->pSibling != NULL)//不為空
{
pCloned->pSibling = pNode->pSibling->pNext;
}
//指向下一個原始結(jié)點
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永遠(yuǎn)指向pClonedNode的后一個結(jié)點
pClonedNode->pNext = pNode->pNext;
pClonedNode = pClonedNode->pNext;
pNode->pNext = pClonedNode->pNext;
pNode = pNode->pNext;
}
return pClonedHead;
}
4.合并函數(shù)
ComplexListPointer Clone(ComplexListPointer pHead)
{
CloneNodes(pHead);
ConnectSiblingNodes(pHead);
return ReconnectNodes(pHead);
}
3.二叉排序樹轉(zhuǎn)換成雙向鏈表
問題：將一棵二叉搜索樹轉(zhuǎn)換成有序的雙向鏈表。不允許使用額外的存儲空間，只能通過移動指針實現(xiàn)。
算法思想
首先，可以看出二叉樹和雙向鏈表的結(jié)構(gòu)很類似，二叉樹的每個結(jié)點有左，右兩個指針，對應(yīng)到雙向鏈表中，左指針就是鏈表結(jié)點指向前一個結(jié)點的指針，右指針就是指向后一個結(jié)點的指針。接下來，分析二叉搜索樹的特點，二叉搜索樹是排好序的，左結(jié)點比根節(jié)點小，右結(jié)點比根節(jié)點大。對該樹進行中序遍歷，就是排好序的了。先對左子樹進行遍歷，遍歷到的最后一個結(jié)點就是左邊子樹最大的結(jié)點，然后將這個結(jié)點接到根結(jié)點，再遍歷右邊子樹，和遍歷左子樹類似。
** 二叉樹的遍歷，一般采用遞歸實現(xiàn)**，所以，這里我們使用遞歸。
代碼
1.定義二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)
//二叉搜索樹定義
typedef struct BinaryTreeNode *NodePointer;
typedef struct BinaryTreeNode
{
int value;
NodePointer left;
NodePointer right;
};
NodePointer root;
2.轉(zhuǎn)換
//轉(zhuǎn)換
BinaryTreeNode* Convert(BinaryTreeNode *root)
{
BinaryTreeNode *pLastNodeInList;//標(biāo)記現(xiàn)有鏈表中的最后一個結(jié)點
if (root != NULL)
{
//每次新遍歷到一個結(jié)點都要改變LastNodeInList指針的指向
//需要傳入地址
ConvertNode(root, &pLastNodeInList);
}
//轉(zhuǎn)換結(jié)束，但是不知道鏈表的頭結(jié)點
//根據(jù)鏈表的LastNodeInList向前遍歷，找到頭結(jié)點
BinaryTreeNode *pHead = pLastNodeInList;
//left指向鏈表中的前一個結(jié)點
while(pHead != NULL && pHead->left !=NULL)
pHead = pHead->left;
return pHead;
}
//轉(zhuǎn)換結(jié)點
/*
node:當(dāng)前要遍歷的結(jié)點；
pLastNodeInList:上一次轉(zhuǎn)換之后的鏈表中的最后一個結(jié)點，也是當(dāng)前鏈表中最大的結(jié)點。
*/
void ConvertNode(BinaryTreeNode *node, BinaryTreeNode **pLastNodeInList)
{
if(node == NULL)
return;
BinaryTreeNode *pCurrent = node;
//中序遍歷左子樹
if(pCurrent->left != NULL)
ConvertNode(pCurrent->left, pLastNodeInList);
//處理根節(jié)點
pCurrent->left = *pLastNodeInList;
//設(shè)置鏈表中上一個結(jié)點的右指針
if(*pLastNodeInList != NULL)
(*pLastNodeInList)->right = pCurrent;
*pLastNodeInList = pCurrent;
//中序遍歷右子樹
if(pCurrent->right != NULL)
ConvertNode(pCurrent->right, pLastNodeInList);
}
總結(jié)
鏈表系列到這里就結(jié)束了，復(fù)雜鏈表列有3道題，和簡單題相比，分析要更多一些，從中我們可以看到，鏈表相關(guān)的題，怎么變都在圍繞指針，所以基本的增加，刪除結(jié)點，遍歷都要很熟悉，再結(jié)合存儲結(jié)構(gòu)的特點，單向鏈表，雙向鏈表，二叉樹，一層層分析優(yōu)化就可以找到解決方法。這也是我最近復(fù)習(xí)的成果，歡迎指教~
