【数据结构|剑指Offer】单向链表的各项操作实现

68 阅读 0 评论 45 点赞

我是靠谱客的博主热心刺猬，最近开发中收集的这篇文章主要介绍【数据结构|剑指Offer】单向链表的各项操作实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本博文着重实现《剑指Offer》上面的单向链表操作。

//数据结构
struct ListNode
{
int data;
ListNode *next;
ListNode(int x) :data(x), next(NULL) {}
};

//在链表尾部添加结点
void AddToTail(ListNode **pHead, int value)
{
ListNode *pNew = new ListNode(value);
assert(pNew != NULL);
if (NULL == *pHead)//原链表为空
*pHead = pNew;
else
{
ListNode *pNode = *pHead;
while (pNode->next)
pNode = pNode->next;
pNode->next = pNew;
}
}

/*单向链表删除操作需要找到前一个结点
二级指针操作是因为会可能修改头结点指针*/
void RemoveNode(ListNode **pHead, int value)
{
if (NULL == pHead || NULL == *pHead)
return;
ListNode *pToDeleted = NULL;
if ((*pHead)->data == value)
{
pToDeleted = *pHead;
*pHead = (*pHead)->next;
}
else
{
ListNode *pNode = *pHead;
while (pNode->next && pNode->next->data != value)//找到待删除结点的前结点
pNode = pNode->next;
if (pNode->next && pNode->next->data == value)
{
pToDeleted = pNode->next;
pNode->next = pNode->next->next;
}
}
if (pToDeleted != NULL)
{
delete pToDeleted;
pToDeleted = NULL;
}
}

//反向打印：递归。链表过长会导致栈溢出
void PrintReverse(ListNode *pHead)
{
if (pHead)
{
PrintReverse(pHead->next);
cout << pHead->data << endl;
}
}
//反向打印：栈
void PrintReverse_iteratively(ListNode *pHead)
{
stack<ListNode *> nodes;
ListNode *pNode = pHead;
while (pNode)
{
nodes.push(pNode);
pNode = pNode->next;
}
while (!nodes.empty())
{
pNode = nodes.top();
cout << pNode->data << endl;
nodes.pop();
}
}

/*
给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点
前提是这个结点是存在于这个链表中，这个由调用者保证
其实现思想：把下一个结点的内容复制到待删除结点上覆盖原有的内容，然后删除下一个结点。
就是操作结点的数据而不是链表的链接关系。平衡二叉树的平衡旋转也是采用这个思想
*/
void DeleteNode(ListNode **pHead, ListNode *pToBeDeleted)
{
if (NULL == pHead || NULL == *pHead)
return;
//要删除的结点不是尾节点
if (pToBeDeleted->next)
{
ListNode *pNext = pToBeDeleted->next;
pToBeDeleted->data = pNext->data;//操作数据而非链接关系
pToBeDeleted->next = pNext->next;
delete pNext;
pNext = NULL;
}
//链表只有一个结点
else if (*pHead == pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pHead = NULL;
}
//链表有多个结点，且待删除结点是尾节点
else//这部分时间复杂度为O(n)，但总的平均时间复杂度为O(1)
{
ListNode *pNode = *pHead;
while (pNode->next != pToBeDeleted)
pNode = pNode->next;
pNode->next = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}

/*输入一个链表，输出该链表中倒数第 k 个结点
思路一：栈*/
ListNode* PrintKNode(ListNode *pHead, int k)
{
if (NULL == pHead || k < 1)
return NULL;
stack<ListNode *> nodes;
ListNode *pNode = pHead;
while (pNode)
{
nodes.push(pNode);
pNode = pNode->next;
}
while (!nodes.empty())
{
--k;
if (0 == k)
{
pNode = nodes.top();
return pNode;
}
nodes.pop();
}
return NULL;
}
/*思路二：快慢指针。快慢指针之间的距离为k-1，当快指针到达尾结点时，慢指针恰好是倒数第k个结点*/
ListNode* FindKthToTail(ListNode *pHead, int k)
{
if (NULL == pHead || k < 1)
return NULL;
ListNode *pAhead = pHead;
ListNode *pBehind = NULL;
for (int i = 0; i < k - 1; ++i)
{
if (pAhead->next)
pAhead = pAhead->next;
else
return NULL;
}
pBehind = pHead;
while (pAhead->next)
{
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}

/*反转链表:输入一个链表的头结点，反转该链表并输出反转后链表的头结点
充分考虑异常情况，尤其是清楚最后反转后的头结点*/
ListNode* ReverseList(ListNode *pHead)
{
if (NULL == pHead || pHead->next == NULL)
return pHead;
ListNode *pPrev = NULL;
ListNode *pNode = pHead;
while (pNode)
{
ListNode *pNext = pNode->next;
pNode->next = pPrev;
pPrev = pNode;//这就是最后反转后的头结点
pNode = pNext;
}
return pPrev;
}

/*合并两个排序的链表，合并后的链表仍是排序好的（递增）*/
/*未排序区的两个链表值小的那个头结点，将是未排序区合并后的头结点，同时也将作为排序区的尾结点。
以此递归，每次只需比较剩下未排序的两个链表的头结点*/
ListNode* MergeList(ListNode *pHead1, ListNode *pHead2)
{
if (NULL == pHead1)
return pHead2;
else if (NULL == pHead2)
return pHead1;
ListNode *pMergedHead = NULL;
if (pHead1->data < pHead2->data)
{
pMergedHead = pHead1;
pMergedHead->next = MergeList(pHead1->next, pHead2);
}
else
{
pMergedHead = pHead2;
pMergedHead->next = MergeList(pHead1, pHead2->next);
}
return pMergedHead;
}

/*输入两个链表，找出它们的第一个公共结点
下面链表L1有6个结点，L2有4个结点，其第一个公共结点为mn1*/
/*
L1:
n1 -> n2 -> n3 -> n4

——> mn1 -> mn2
/
L2:
m1 -> m2
*/
/*
实现思想：长的链表先前进若干结点到与短链表等长位置，然后同步前进
充分考虑异常情况
*/
int GetLength(ListNode *pHead)
{
int leng = 0;
while (pHead)
{
leng++;
pHead = pHead->next;
}
return leng;
}
ListNode* FindFirstCommonNode(ListNode *L1, ListNode *L2)
{
if (NULL == L1 || NULL == L2)
return NULL;
int leng1 = GetLength(L1);
int leng2 = GetLength(L2);
int distance = (leng1 > leng2) ? leng1 - leng2 : leng2 - leng1;
ListNode *pFirst = NULL, *pSecond = NULL;
if (leng1 > leng2)
{
pFirst = L1;
pSecond = L2;
}
else
{
pFirst = L2;
pSecond = L1;
}
while (distance--)//考虑非公共部分长度一样情况
{
pFirst = pFirst->next;
}
while (pFirst && pSecond)
{
if (pFirst == pSecond)//寻找第一个公共结点
return pFirst;
pFirst = pFirst->next;
pSecond = pSecond->next;
}
return NULL;//不存在公共结点情况
}

/*链表中环的入口结点
最常规解法：快慢指针，关键在于定位环的入口结点，
具体分析参见博文：http://blog.csdn.net/wenqian1991/article/details/17452715 */
ListNode* EntryNodeOfLoop(ListNode *pHead)
{
if (NULL == pHead)
return NULL;
ListNode *pFast = pHead;
ListNode *pSlow = pHead;
//判断是否有环
while (pFast->next)//两种情况跳出循环
{
pFast = pFast->next->next;
pSlow = pSlow->next;
if (NULL == pFast)
return NULL;
if (pFast == pSlow)//有环
break;
}
if (NULL == pFast->next)//没环
return NULL;
//寻找环的入口结点
/*快指针移动至链表头结点，同时两结点以相同速度再次相遇就是环的开始节点
http://blog.csdn.net/wenqian1991/article/details/17452715 */
pFast = pHead;
while (pFast != pSlow)
{
pFast = pFast->next;
pSlow = pSlow->next;
}
return pFast;
}