1. 求单链表中结点的个数
//2. 将单链表反转
//3. 查找单链表中的倒数第K个结点（k > 0）
//4. 查找单链表的中间结点
//5. 从尾到头打印单链表
//6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
//7. 判断一个单链表中是否有环
//8. 判断两个单链表是否相交
//9. 求两个单链表相交的第一个节点
//10. 已知一个单链表中存在环，求进入环中的第一个节点
//11. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted
//12. 使用链表实现约瑟夫环(JosephCircle)问题
//6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
//这个类似归并排序。尤其注意两个链表都为空，和其中一个为空时的情况。只需要O（1）的空间。时间复杂度为O（max(len1, len2)）。参考代码如下：
// 合并两个有序链表
ListNode * mergeList(ListNode * pHead1, ListNode * pHead2)
{
if (nullptr == pHead1)
{
return pHead2;
}
if (nullptr == pHead2)
{
return pHead1;
}
// 定义合并后的链表的头结点
ListNode * pMergeHead = nullptr;
ListNode * pNode1 = pHead1;// 遍历第一条链表
ListNode * pNode2 = pHead2;// 遍历第二条链表
// 1.确定合并后的头结点
if (pNode1->m_nKey<= pNode2->m_nKey)
{
// 记录pNode1的后继
ListNode * pTemp = pNode1->m_pNext;
pMergeHead = pNode1;// 头结点为pNode1
pNode1->m_pNext= nullptr;//
pNode1 = pTemp;
}
else
{
// 记录pNode2的后继
ListNode * pTemp = pNode2->m_pNext;
pMergeHead = pNode2;// 头结点为pNode2
pNode2->m_pNext= nullptr;//
pNode2 = pTemp;
}
// 记录插入的位置(插入在之后)
ListNode * pCur = pMergeHead;
// 2.其他元素的排列
while (pNode1 != nullptr && pNode2 != nullptr)
{
if (pNode1->m_nKey<= pNode2->m_nKey)
{
// 记录pNode1的后继
ListNode * pTemp = pNode1->m_pNext;
// pNode1插入在pCur的后面
pCur->m_pNext= pNode1;
pNode1->m_pNext= nullptr;
// 修改pCur
pCur = pNode1;
pNode1 = pTemp;
}
else
{
// 记录pNode2的后继
ListNode * pTemp = pNode2->m_pNext;
// pNode2插入在pCur的后面
pCur->m_pNext= pNode2;
pNode2->m_pNext= nullptr;
// 修改pCur
pCur = pNode2;
pNode2 = pTemp;
}
}
// 3.剩余的部分的接入
if (pNode1 != nullptr)
{
pCur->m_pNext= pNode1;
}
else if (pNode2 != nullptr)
{
pCur->m_pNext= pNode2;
}
return pMergeHead;
}
//也有如下递归解法：
ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)
{
if (pHead1 == NULL)
return pHead2;
if (pHead2 == NULL)
return pHead1;
ListNode * pHeadMerged = NULL;
if (pHead1->m_nKey < pHead2->m_nKey)
{
pHeadMerged = pHead1;
pHeadMerged->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);
}
else
{
pHeadMerged = pHead2;
pHeadMerged->m_pNext = MergeSortedList(pHead1, pHead2->m_pNext);
}
return pHeadMerged;
}
//7. 判断一个单链表中是否有环
//这里也是用到两个指针。如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。时间复杂度为O（n）。参考代码如下：
bool HasCircle(ListNode * pHead)
{
ListNode * pFast = pHead; // 快指针每次前进两步
ListNode * pSlow = pHead; // 慢指针每次前进一步
while (pFast != NULL && pFast->m_pNext != NULL)
{
pFast = pFast->m_pNext->m_pNext;
pSlow = pSlow->m_pNext;
if (pSlow == pFast) // 相遇，存在环
return true;
}
return false;
}
//8. 判断两个单链表是否相交
//如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。时间复杂度为O(len1 + len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为O(1)。参考代码如下：
bool IsIntersected(ListNode * pHead1, ListNode * pHead2)
{
if (pHead1 == NULL || pHead2 == NULL)
return false;
ListNode * pTail1 = pHead1;
while (pTail1->m_pNext != NULL)
pTail1 = pTail1->m_pNext;
ListNode * pTail2 = pHead2;
while (pTail2->m_pNext != NULL)
pTail2 = pTail2->m_pNext;
return pTail1 == pTail2;
}
//9. 求两个单链表相交的第一个节点
//对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。
//对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。
//两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1 - len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同。
//时间复杂度，O(len1 + len2)。参考代码如下：
ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)
{
if (pHead1 == NULL || pHead2 == NULL)
return NULL;
int len1 = 1;
ListNode * pTail1 = pHead1;
while (pTail1->m_pNext != NULL)
{
pTail1 = pTail1->m_pNext;
len1++;
}
int len2 = 1;
ListNode * pTail2 = pHead2;
while (pTail2->m_pNext != NULL)
{
pTail2 = pTail2->m_pNext;
len2++;
}
if (pTail1 != pTail2) // 不相交直接返回NULL
return NULL;
ListNode * pNode1 = pHead1;
ListNode * pNode2 = pHead2;
// 先对齐两个链表的当前结点，使之到尾节点的距离相等
if (len1 > len2)
{
int k = len1 - len2;
while (k--)
pNode1 = pNode1->m_pNext;
}
else
{
int k = len2 - len1;
while (k--)
pNode2 = pNode2->m_pNext;
}
while (pNode1 != pNode2)
{
pNode1 = pNode1->m_pNext;
pNode2 = pNode2->m_pNext;
}
return pNode1;
}
//10. 已知一个单链表中存在环，求进入环中的第一个节点
//首先判断是否存在环，若不存在结束。在环中的一个节点处断开（当然函数结束时不能破坏原链表），这样就形成了两个相交的单链表，求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。参考代码如下：
ListNode* GetFirstNodeInCircle(ListNode * pHead)
{
if (pHead == NULL || pHead->m_pNext == NULL)
return NULL;
ListNode * pFast = pHead;
ListNode * pSlow = pHead;
while (pFast != NULL && pFast->m_pNext != NULL)
{
pSlow = pSlow->m_pNext;
pFast = pFast->m_pNext->m_pNext;
if (pSlow == pFast)
break;
}
if (pFast == NULL || pFast->m_pNext == NULL)
return NULL;
// 将环中的此节点作为假设的尾节点，将它变成两个单链表相交问题
ListNode * pAssumedTail = pSlow;
ListNode * pHead1 = pHead;
ListNode * pHead2 = pAssumedTail->m_pNext;
ListNode * pNode1, *pNode2;
int len1 = 1;
ListNode * pNode1 = pHead1;
while (pNode1 != pAssumedTail)
{
pNode1 = pNode1->m_pNext;
len1++;
}
int len2 = 1;
ListNode * pNode2 = pHead2;
while (pNode2 != pAssumedTail)
{
pNode2 = pNode2->m_pNext;
len2++;
}
pNode1 = pHead1;
pNode2 = pHead2;
// 先对齐两个链表的当前结点，使之到尾节点的距离相等
if (len1 > len2)
{
int k = len1 - len2;
while (k--)
pNode1 = pNode1->m_pNext;
}
else
{
int k = len2 - len1;
while (k--)
pNode2 = pNode2->m_pNext;
}
while (pNode1 != pNode2)
{
pNode1 = pNode1->m_pNext;
pNode2 = pNode2->m_pNext;
}
return pNode1;
}
//11. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted
//对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)。参考代码如下：
void Delete(ListNode * pHead, ListNode * pToBeDeleted)
{
if (pToBeDeleted == NULL)
return;
if (pToBeDeleted->m_pNext != NULL)
{
pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey; // 将下一个节点的数据复制到本节点，然后删除下一个节点
ListNode * temp = pToBeDeleted->m_pNext;
pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;
delete temp;
}
else // 要删除的是最后一个节点
{
if (pHead == pToBeDeleted) // 链表中只有一个节点的情况
{
pHead = NULL;
delete pToBeDeleted;
}
else
{
ListNode * pNode = pHead;
while (pNode->m_pNext != pToBeDeleted) // 找到倒数第二个节点
pNode = pNode->m_pNext;
pNode->m_pNext = NULL;
delete pToBeDeleted;
}
}
}
// 12.使用链表实现约瑟夫环(JosephCircle)问题：
ListNode* JosephCircle(ListNode* pHead,unsigned int k);
(约瑟夫环：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到k的那个人出列；他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，直到圆桌周围的人只剩下一个人。)
答案：
ListNode* JosephCircle(ListNode* pHead,unsigned int k)
{
ListNode* pCur = pHead; //构建环
while (pCur->m_pNext != NULL)
{
pCur = pCur->m_pNext;
}
pCur->m_pNext = pHead;
pCur = pHead;
while (pCur ->m_pNext != pCur) // 只有一个结点时跳出循环
{
unsigned int i = k;
while (--i)
{
pCur = pCur ->m_pNext;
}
//将后一个结点的数据域和指针域赋值给要删除的结点，删除后一个节点
ListNode* pDel = pCur ->m_pNext;
pCur ->m_pNext = pDel ->m_pNext;
pCur ->m_nKey = pDel->m_nKey;
delete pDel ;
pDel = NULL;
}
pCur ->m_pNext = NULL;
return pCur;
}
1-5在上一期哦，谢谢大家！