好多天沒(méi)有更新文章，今天更新的是鏈表的復(fù)雜算法題，這一篇完了之后年碘，鏈表相關(guān)的也結(jié)束了，會(huì)進(jìn)入下一個(gè)環(huán)節(jié)展鸡。
- 圓圈中最后剩下的數(shù)字
- 復(fù)雜鏈表的復(fù)制
- 二叉排序樹轉(zhuǎn)換成雙向鏈表
1. 圓圈中最后剩下的數(shù)字
問(wèn)題描述：0,1,2,...,n-2,n-1這n個(gè)數(shù)字排成一個(gè)圓圈，從數(shù)字0開始埃难，每次刪除圓圈中的第m個(gè)數(shù)字莹弊。求出圓圈中最后剩下的 一個(gè)數(shù)字。如圖：
每次刪除第3個(gè)數(shù)字涡尘，刪除順序依次是2忍弛，0，4考抄，1细疚，最后剩下的數(shù)字是3。
算法思想
思路一：用鏈表模擬數(shù)字排成圓圈的數(shù)據(jù)結(jié)構(gòu)川梅，就是一個(gè)環(huán)形鏈表疯兼。從鏈表的頭結(jié)點(diǎn)開始，每刪除一個(gè)結(jié)點(diǎn)需要m步運(yùn)算（從鏈表的第一個(gè)結(jié)點(diǎn)開始遍歷）贫途，鏈表中一共有n個(gè)結(jié)點(diǎn)吧彪，時(shí)間復(fù)雜度為O(mn)。這一種思想的實(shí)現(xiàn)要簡(jiǎn)單一些丢早，也比較耗時(shí)一些姨裸。
思路二：第二種思路主要是找到每次刪除的規(guī)律，更像一種數(shù)學(xué)歸納怨酝。首先定義以下概念：
f(n,m): 表示在n個(gè)圍成圈的數(shù)字中每次刪除第m個(gè)數(shù)字之后傀缩，最后剩下的數(shù)字。很顯然农猬，第一次刪除的數(shù)字是(m-1)%n,記作k赡艰。
f '(n-1,m): 表示第一次刪除第m個(gè)幾點(diǎn)之后，在剩下的n-1個(gè)數(shù)字中斤葱，每次刪除第k個(gè)數(shù)字的最后剩下的數(shù)字瞄摊。為什么要用不同的函數(shù)表示呢？因?yàn)榈谝淮蝿h除k之后苦掘，剩下的數(shù)字序列為k+1,k+2,...,n-2,n-1,0,1,...,k-1换帜，數(shù)字不再是從0開始了。
p(x)=x-k-1: 是刪除第一個(gè)數(shù)字之后鹤啡，剩下的n-1個(gè)數(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ù)字一定是刪除一個(gè)數(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個(gè)运杭，下一次還是從0開始的序列，所以最后剩下的數(shù)字一定是0.
兩種方法相比函卒，第一種思路更好理解辆憔，第二種思路更創(chuàng)新，通過(guò)找到規(guī)律來(lái)解題报嵌，但是分析要困難一些虱咧。
代碼
第一種思路的代碼。
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個(gè)結(jié)點(diǎn)彤钟。
//使用鏈表
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;
}
第二種思路的代碼跷叉，可以看到逸雹，分析很難，但是代碼很簡(jiǎn)單
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個(gè)數(shù)字
{
last = (last + m) % i;
}
printf("LastRemaining：%d ", last);
return last;
}
2. 復(fù)雜鏈表的復(fù)制
問(wèn)題：有這樣一個(gè)復(fù)雜鏈表云挟，每個(gè)結(jié)點(diǎn)除了pNext這個(gè)指向下一個(gè)結(jié)點(diǎn)的指針外梆砸，還有pSibling這個(gè)指向鏈表中任意結(jié)點(diǎn)或者NULL的指針。完成這樣一個(gè)復(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é)點(diǎn)沸枯，使用pNext連接起來(lái)日矫，第二步是復(fù)制pSibling指針。在復(fù)制pSibling的時(shí)候绑榴，需要注意哪轿，這里會(huì)有一個(gè)O(n)的遍歷。假設(shè)原鏈表中一個(gè)結(jié)點(diǎn)的pSibling指向的結(jié)點(diǎn)是s,我們不知道s在原鏈表中是哪個(gè)結(jié)點(diǎn)翔怎，需要遍歷原鏈表找到s,才能完成復(fù)制窃诉。每個(gè)結(jié)點(diǎn)的pSibling指針的復(fù)制都需要O(n)的遍歷杨耙，整個(gè)算法的時(shí)間復(fù)雜度為O(n^2).
思路二：對(duì)常規(guī)思路的優(yōu)化。上一種方法的時(shí)間花費(fèi)主要是在定位pSibling上飘痛，如果能減少定位用的時(shí)間珊膜，效率也會(huì)變高。我們可以使用hash表來(lái)優(yōu)化宣脉。第一步還是先復(fù)制鏈表上的所有結(jié)點(diǎn)车柠，用pNext連接，假設(shè)原始鏈表上的結(jié)點(diǎn)N復(fù)制之后的結(jié)點(diǎn)是N'塑猖，使用hash表保存<N,N'>的對(duì)應(yīng)關(guān)系竹祷。第二步還是設(shè)置鏈表中每個(gè)結(jié)點(diǎn)的pSibling。原始鏈表中結(jié)點(diǎn)N的pSibling指向的結(jié)點(diǎn)S萌庆，那么復(fù)制之后的結(jié)點(diǎn)N'的pSibling指向的就是S'，由于有hash表币旧，我們可以在O(1)時(shí)間內(nèi)根據(jù)S找到S'.這里是使用空間換時(shí)間践险，需要O(n)的輔助存儲(chǔ)空間。
思路三：不需要額外的存儲(chǔ)空間能不能完成這個(gè)題目呢吹菱？這就是思路三了巍虫。第一步，復(fù)制每個(gè)結(jié)點(diǎn)鳍刷，并把復(fù)制的結(jié)點(diǎn)接在原始結(jié)點(diǎn)的后面占遥。如圖，
第二步输瓜，設(shè)置結(jié)點(diǎn)的pSibling指針瓦胎，因?yàn)閺?fù)制之后的結(jié)點(diǎn)N'在原始結(jié)點(diǎn)N的下一個(gè)，那么結(jié)點(diǎn)N的pSibling是S尤揣，對(duì)應(yīng)的復(fù)制之后的結(jié)點(diǎn)S'就是S->pNext搔啊。如圖，
第三步北戏，將原鏈表和復(fù)制之后的鏈表分離负芋。
代碼
這里貼的是第三種思路的代碼。我們可以將每一步定義為一個(gè)函數(shù)嗜愈，分步驟解決問(wèn)題旧蛾。
1.復(fù)制結(jié)點(diǎn)，插入到原結(jié)點(diǎn)后面蠕嫁。
//復(fù)制鏈表中的結(jié)點(diǎn)
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í)不設(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é)點(diǎn)
ComplexListPointer pCloned = pNode->pNext;
if(pNode->pSibling != NULL)//不為空
{
pCloned->pSibling = pNode->pSibling->pNext;
}
//指向下一個(gè)原始結(jié)點(diǎn)
pNode = pCloned->pNext;
}
}
3.拆分鏈表
//拆分兩個(gè)鏈表
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的后一個(gè)結(jié)點(diǎn)
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)換成雙向鏈表
問(wèn)題：將一棵二叉搜索樹轉(zhuǎn)換成有序的雙向鏈表。不允許使用額外的存儲(chǔ)空間剃毒，只能通過(guò)移動(dòng)指針實(shí)現(xiàn)绍绘。
算法思想
首先，可以看出二叉樹和雙向鏈表的結(jié)構(gòu)很類似，二叉樹的每個(gè)結(jié)點(diǎn)有左陪拘，右兩個(gè)指針厂镇，對(duì)應(yīng)到雙向鏈表中，左指針就是鏈表結(jié)點(diǎn)指向前一個(gè)結(jié)點(diǎn)的指針左刽，右指針就是指向后一個(gè)結(jié)點(diǎn)的指針捺信。接下來(lái)，分析二叉搜索樹的特點(diǎn)欠痴，二叉搜索樹是排好序的迄靠，左結(jié)點(diǎn)比根節(jié)點(diǎn)小，右結(jié)點(diǎn)比根節(jié)點(diǎn)大喇辽。對(duì)該樹進(jìn)行中序遍歷掌挚，就是排好序的了。先對(duì)左子樹進(jìn)行遍歷菩咨，遍歷到的最后一個(gè)結(jié)點(diǎn)就是左邊子樹最大的結(jié)點(diǎn)吠式，然后將這個(gè)結(jié)點(diǎn)接到根結(jié)點(diǎn)，再遍歷右邊子樹抽米，和遍歷左子樹類似特占。
** 二叉樹的遍歷，一般采用遞歸實(shí)現(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)有鏈表中的最后一個(gè)結(jié)點(diǎn)
if (root != NULL)
{
//每次新遍歷到一個(gè)結(jié)點(diǎn)都要改變LastNodeInList指針的指向
//需要傳入地址
ConvertNode(root, &pLastNodeInList);
}
//轉(zhuǎn)換結(jié)束标捺，但是不知道鏈表的頭結(jié)點(diǎn)
//根據(jù)鏈表的LastNodeInList向前遍歷懊纳，找到頭結(jié)點(diǎn)
BinaryTreeNode *pHead = pLastNodeInList;
//left指向鏈表中的前一個(gè)結(jié)點(diǎn)
while(pHead != NULL && pHead->left !=NULL)
pHead = pHead->left;
return pHead;
}
//轉(zhuǎn)換結(jié)點(diǎn)
/*
node:當(dāng)前要遍歷的結(jié)點(diǎn)；
pLastNodeInList:上一次轉(zhuǎn)換之后的鏈表中的最后一個(gè)結(jié)點(diǎn)亡容，也是當(dāng)前鏈表中最大的結(jié)點(diǎn)长踊。
*/
void ConvertNode(BinaryTreeNode *node, BinaryTreeNode **pLastNodeInList)
{
if(node == NULL)
return;
BinaryTreeNode *pCurrent = node;
//中序遍歷左子樹
if(pCurrent->left != NULL)
ConvertNode(pCurrent->left, pLastNodeInList);
//處理根節(jié)點(diǎn)
pCurrent->left = *pLastNodeInList;
//設(shè)置鏈表中上一個(gè)結(jié)點(diǎn)的右指針
if(*pLastNodeInList != NULL)
(*pLastNodeInList)->right = pCurrent;
*pLastNodeInList = pCurrent;
//中序遍歷右子樹
if(pCurrent->right != NULL)
ConvertNode(pCurrent->right, pLastNodeInList);
}
總結(jié)
鏈表系列到這里就結(jié)束了，復(fù)雜鏈表列有3道題萍倡，和簡(jiǎn)單題相比身弊，分析要更多一些，從中我們可以看到列敲，鏈表相關(guān)的題阱佛，怎么變都在圍繞指針，所以基本的增加戴而，刪除結(jié)點(diǎn)凑术，遍歷都要很熟悉，再結(jié)合存儲(chǔ)結(jié)構(gòu)的特點(diǎn)所意，單向鏈表淮逊，雙向鏈表催首，二叉樹，一層層分析優(yōu)化就可以找到解決方法泄鹏。這也是我最近復(fù)習(xí)的成果郎任，歡迎指教~
