一、复制复杂链表
已知一个复杂链表，每个节点有一个指针pNextt指向下一个结点，同时它还有一个指针pSibling指向链表中的任意一个结点或者NULL。实现一个函数实现这个复杂链表的复制。
复杂链表：
struct ComplexLinkNode{
int value;
ComplexLinkNode * pNext;
ComplexLinkNode * pSilbing;
}
方法一：
复制所有结点先用pNext连接起来，因为pSibling指向的结点是任意的，必须保证在确定一个结点的pSibing前先将所有结点确定。设原链表的结点为N，N的pSibing为S，复制的链表的节点为N'，N' 的pSibing为S‘。接下来依次确定每个结点N' 的pSibing，我们需要从第一个结点first开始遍历直至找到一个结点S’，它是N' 的pSibing，再将N‘ 的pSibing指向S’。因为每个结点N' 的pSibing可能在其前面也可能在其后面，所以每次遍历都要从第一个结点开始。这样确定每个结点N'
的pSibing的时间复杂度为O(n)，总的时间复杂度为O(n²)；
方法二：
首先也是先复制所有结点然后用pNext链接起来，在复制的时候我们建立一个哈希表，其中存放的是<N,N'>的配对信息；然后我们确定N' 的pSibing，如果在原链表中N的pSibing指向S，那么N' 的pSibing指向S' ，有了哈希表，我们可以在时间O(1)找到S' 。我们用O(n)的空间复杂度将时间复杂度降为O(n)。
方法三：
首先复制所有结点，然后将这些结点作为原结点的pNext插入，也即如果原链表为A -> B -> C，那么复制后的链表为A -> A' -> B -> B' -> C -> C' ，这样如果A的pSibing指向C，那么A' 的pSibing就指向C‘。
代码：
ComplexLinkNode* CopyCLink(ComplexLinkNode * pHead){
CloneNodes(pHead);
setPSibling(pHead);
return DepartLink(pHead);
}
void CloneNodes(ComplexLinkNode * pHead){
ComplexLinkNode * pNode = pHead;
while(pNode != NULL){
ComplexLinkNode * newNode = new ComplexLinkNode();
newNode -> value = pNode -> value;
newNode -> pNext = pNode -> pNext;
newNode -> pSilbing = NULL;
pNode -> pNext = newNode;
pNode = newNode -> pNext;
}
}
void setPSibling(ComplexLinkNode * pHead){
ComplexLinkNode * pNode = pHead;
while(pNode != NULL){
pNode -> pNext -> pSibling = pNode -> pSibling -> pNext;
pNode = pNode -> pNext -> pNext;
}
}
ComplexLinkNode * DepartLink(ComplexLinkNode * pHead){
if(pHead == NULL)
return NULL;
ComplexLinkNode * pHeadOfClone = pHead -> pNext;
ComplexLinkNode * pNode = pHeadOfClone -> pNext;
ComplexLinkNode * pNodeOfClone = pHeadOfClone;
while(pNode != NULL){
pNodeOfClone -> pNext = pNode -> pNext;
pNode -> pNext = pNodeOfClone -> pNext -> pNext;
}
return pHeadOfClone;
/*
ComplexLinkNode * pHead1 = pHead;
if(pHead == NULL)
return pHead;
错误代码，未考虑到原链表只有一个结点的情况
ComplexLinkNode * pHead2 = pHead -> pNext;
while(pHead1 != NULL && pHead2 != NULL)[{
pHead1 -> pNext = pHead2 -> pNext;
pHead2 -> pNext = pHead1 -> pNext -> pNext;
}
pHead = pHead1;
return pHead2;
*/
}
二、二叉搜索树和双向链表
输入一个二叉搜索树，将它转换为一个排序的双向链表，不能创建新的结点，只能调整树中结点的指向。
//为什么写成两个函数，因为我们需要一个参数，它是指向当前链表最后一个元素的指针，而且这个是共享的
BinaryTreeNode * ConvertToLink(BinaryTreeNode * pRoot){
BinaryTreeNode * pLastNode = NULL;
CTL(pRoot,&pLastNode);
BinaryTreeNode * pHeadOfLink = pLastNode;
while(pHeadOfLink != NULL && pHeadOfLink -> left != NULL)
pHeadOfLink = pHeadOfLink -> left;
return pHeadOfLink;
}
//中序遍历就是先看左子树再看根结点再看右子树，所以在下面的处理方式就是左、根、右
//每一个叶子结点都看成没有左右子树的根结点，对它的操作就是把该结点的左指针指向pLastNode,
//然后让它作为链表的pLastNode
void CTL(BinaryTreeNode * pRoot,BinaryTreeNode ** pLastNode){
if(pRoot == NULL)
return NULL;
if(pRoot -> left != NULL)
CTL(pRoot -> left,pLastNode);
if(*pLastNode != NULL)
(*pLastNode) -> right = pRoot;
pRoot -> left = *pLastNode;
*pLastNode = pRoot;
if(pRoot -> right != NULL)
CTL(pRoot -> right,pLastNode);
}
另一种递归实现，比较好理解：
（1）如果二叉树查找树为空，不需要转换，对应双向链表的第一个节点是NULL，最后一个节点是NULL
（2）如果二叉查找树不为空：
如果左子树为空，对应双向有序链表的第一个节点是根节点，左边不需要其他操作；
如果左子树不为空，转换左子树，二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点，同时将根节点和左子树转换后的双向有序链 表的最后一个节点连接；
如果右子树为空，对应双向有序链表的最后一个节点是根节点，右边不需要其他操作；
如果右子树不为空，对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点，同时将根节点和右子树转换后的双向有序链表的第一个节点连 接。
//这个函数的作用是将以root为根节点的树转换为一个起始节点为pFirstNode,终止节点为pLastNode的双向链表
void convertBt(BiNode * root,BiNode* & pFirstNode,BiNode* & pLastNode){
//如果该节点为空,那么转换之后的链表的起始和终止节点都为NULL
if(root == NULL){
pFirstNode = NULL;
pLastNode = NULL;
return;
}
BiNode* pFirstNodeLeft,*pLastNodeLeft,*pFirstNodeRight,*pLastNodeRight;
//如果左子树不为空,那么将其转换为一个起始和终止节点分别为pFirstNodeLeft和pLastNodeLeft的链表,并对指针进行调整
if(root ->lchild != NULL){
convertBt(root ->lchild,pFirstNodeLeft,pLastNodeLeft);
pFirstNode = pFirstNodeLeft;
pLastNodeLeft ->rchild = root;
root ->lchild = pLastNodeLeft;
}else{
//如果左子树为空,那么对应有序链表的第一个节点就是根节点
pFirstNode = root;
}
if(root ->rchild != NULL){
convertBt(root ->rchild,pFirstNodeRight,pLastNodeRight);
pLastNode = pLastNodeRight;
pFirstNodeRight ->lchild = root;
root ->rchild = pFirstNodeRight;
}else{
pLastNode = root;
}
return;
}
void convertBt(BiNode * root){
BiNode* pFirstNode,* pLastNode;
convertBt(root,pFirstNode,pLastNode);
BiNode * node;
for(node = pFirstNode;node != NULL;node = node ->rchild)
printf("%d ",node ->data);
}
自己写的根据中序遍历实现方法，但是需要创建一个节点：
void convert(BiNode * root){
if (root == NULL)
return;
BiNode * node = root;
//该节点是最后整个链表的头节点
BiNode * nodeStart = new BiNode();
nodeStart ->lchild = NULL;
nodeStart ->rchild = NULL;
//nodeStart指向链表头节点,nodeEnd指向最后一个节点
BiNode * nodeEnd = nodeStart;
std::stack<BiNode*> nodes;
while(node != NULL || !nodes.empty()){
while(node != NULL){
nodes.push(node);
node = node ->lchild;
}
//此方法核心在于在中序遍历过程中对指针进行修改
node = nodes.top();
nodes.pop();
//取出栈顶元素链接到链表的最后
nodeEnd ->rchild = node;
node ->lchild = nodeEnd;
//链表最后一个元素也要相应发生变化
nodeEnd = node;
//这句是中序遍历常规语句
node = node ->rchild;
}
BiNode * temp;
for(temp = nodeStart->rchild; temp != NULL;temp = temp->rchild)
printf("%d ",temp ->data);
}
三、给单向链表排序
代码：
LinkList * LinkListSort(LinkList * pHead){
if(pHead == NULL)
return pHead;
LinkList * pHeadAS = NULL; //排序后链表的头结点
LinkList * pTail = NULL； //排序后链表的尾结点
LinkList * pMin; //存放每次遍历得到的最小结点
LinkList * pMinFront; //存放最小结点前一个结点
LinkList * pNode; //用于遍历链表的结点
while(pHead != NULL){
for(pNode = pHead,pMin = pHead;pNode -> next != NULL; pNode = pNode -> next){
if(pNode -> next -> value < pMin -> value){
pMinFront = pNode;
pMin = pNode -> next;
}
}
if(pHeadAS == NULL){ //若排序后的链表为空，那么就把pHeadAS指向pMin，反之将pMin链接到pHeadAS后
pHeadAS = pMin;
pTail = pMin;
}else{
pTail -> next = pMin;
pTail = pMin;
}
if(pMin == pHead){ //如果最小的结点是原链表的头结点，那么要改变pHead，反之直接让pMin前面的结点指向
//pMin->next，这里考虑了链表只有一个结点的情况
pHead = pHead -> next;
}else{
pMinFront -> next = pMin -> next;
}
}
if(pHead == NULL)
pTail -> next = NULL;
return pHeadAS;
}
四、在O(1)时间内删除链表结点
给定链表的头指针和一个结点指针，定义一个函数在O(1)时间内删除该结点。
单向链表中删除某个节点最常规做法是从头遍历查找要删除结点，然后在链表中删除之。这种情况下由于需要遍历，时间复杂度为O(n)。之所以要查找，是因为我们要找到要删除结点的前一个结点。这个问题也适用于：只给定一个结点但是不给定头指针的链表的结点删除问题。
void DeleteNode(LinkNode ** pHead,LinkNode * pToBeDeleted){
if(*pHead == NULL || pToBeDeleted == NULL)
return;
LinkNode * pNext = pToBeDeleted -> next;
if(pNext != NULL){
pToBeDeleted -> next = pNext -> next;
pToBeDeleted -> value = pNext -> value;
delete pNext;
pNext = NULL;
}elseif(pToBeDeleted == *pHead){
//这里是链表中只有一个头结点的情况
delete pToBeDeleted;
pToBeDeleted = NULL;
*pHead = NULL;
}
else{
pNode = *pHead;
while(pNode -> next != pToBeDeleted)
pNode = pNode -> next;
pNode -> next = NULL;
pToBeDeleted = NULL;
}
}
时间复杂度分析：对于n-1个非尾结点而言，我们可以在时间O(1)内把要删除结点下一个节点的内存复制覆盖要删除的结点，并删除下一个结点，对于尾结点而言，由于仍然需要顺序查找，因此时间复杂度为O(n)，因此总的时间复杂度为[(n-1)*O(1)+O(n)]/n=O(1)。但是这段代码基于一种假设，那就是要删除的节点在链表中，我们需要O(n)的时间才能判断链表中是否包含这个节点。