单链表
- 单链表问题与思路
-
找出单链表的倒数第K个元素（仅允许遍历一遍链表）
使用指针追赶的方法。定义两个指针fast和slow，fast先走K步，然后fast和slow同时继续走。当fast到链表尾部时，slow指向倒数第K个。注意要考虑链表长度应该大于K -
找出单链表的中间元素（仅允许遍历一遍链表）
使用指针追赶的方法。fast每次走一步，slow每次走两步。当fast到链表尾部时，slow指向链表的中间元素。
-
判断单链表是否有环？
方法一：使用指针追赶的方法。slow指针每次走一步，fast指针每次走两步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
方法二：使用p、q两个指针，p总是向前走，但q每次都从头开始走。 -
如何知道环的长度？
记录下碰撞点（或者找在环中任意一结点都可以），让slow从碰撞点开始，绕着环走一圈，再次到碰撞点的位置时，所走过的结点数就是环的长度s。 -
如何找到环的入口？
分别从碰撞点、头指针开始走，相遇的那个点就是连接点。 -
判断两个链表（无环）是否相交？
方法一：采用暴力的方法，遍历两个链表，在遍历的过程中进行比较，看节点是否相同。方法二：两链表一旦相交，相交节点一定有相同的内存地址，因此利用内存地址建立哈希表，如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是：遍历第一个链表，并利用地址建立哈希表，遍历第二个链表，看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。时间复杂度O(（length（A）+ length（B))
方法三：问题转化法。先遍历第一个链表到其尾部，然后将尾部的原本指向NULL的next指针指向第二个链表。这样两个链表就合成了一个链表，问题转变为判断新的链表是否有环？
方法四：一旦两个链表相交，那么两个链表从相交节点开始到尾节点一定都是相同的节点。所以，如果他们相交的话，那么他们最后的一个节点一定是相同的，因此分别遍历到两个链表的尾部，然后判断他们是否相同。
-
如何知道两个单链表（可能有环）是否相交
思路：根据两个链表是否有环来分别处理，若相交这个环属于两个链表共有
（1）如果两个链表都没有环。
（2）一个有环，一个没环。肯定不相交
（3）两个都有环。
①求出A的环入口，判断其是否在B链表上，如果在，则相交。
② 在A链表上，使用指针追赶的方法，找到两个指针碰撞点，之后判断碰撞点是否在B链表上。如果在，则相交。 -
寻找两个相交链表的第一个公共节点
方法一：最简单的方法就是先顺序访问其中一个链表，在每访问一个节点时，都对另外一个链表进行遍历，直到找到一个相等的节点位置，如果链表长度分别是m,n 则时间复杂度为O(mn)。
方法二：（两种情况）
① 相交的点，在环外。如果两个链表有公共节点，那么该公共节点之后的所有节点都是两个链表所共有的，所以长度一定也是相等的，如果两个链表的总长度是相等的，那么我们对两个链表进行遍历，则一定同时到达第一个公共节点。但是链表的长度实际上不一定相同，所以计算出两个链表的长度之差n，然后让长的那个链表先移动n步，短的链表再开始向后遍历，这样他们一定同时到达第一个公共节点，我们只需要在向后移动的时候比较两个链表的节点是否相等就可以获得第一个公共节点。时间复杂度是O(m+n)。
② 相交的点在环内。当交点在环中时，此时的交点可以是A链表中的环入口点，也可以是B链表中环入口点。这是因为如果把B看出一个完整的链表，而A指向了B链表，则此时交点是A的环入口点。反之交点是链表B的环入口点。
思路：根据上述分析，可以直接求出A的环入口点或者B的环入口点就可以了。
- 单链表代码实现
链表结点声明如下：
struct ListNode{
int m_nKey;
ListNode * m_pNext;
};
- 求单链表中结点的个数
这是最最基本的了，应该能够迅速写出正确的代码，注意检查链表是否为空。时间复杂度为O（n）。参考代码如下：
1. // 求单链表中结点的个数
2. unsigned int GetListLength(ListNode * pHead)
3. {
4. if(pHead == NULL)
5. return 0;
6.
7. unsigned int nLength = 0;
8. ListNode * pCurrent = pHead;
9. while(pCurrent != NULL)
10. {
11. nLength++;
12. pCurrent = pCurrent->m_pNext;
13. }
14. return nLength;
15. }
- 找到单链表的中间节点：
SListNode* FindMidNode(SListNode* pHead)//pHead是链表的头节点
{
SListNode* fast = pHead;
SListNode* slow = pHead;
while (fast->next)
{
slow = slow->next;
fast = fast->next;
if (fast->next)
{
fast = fast->next;
}
else
{
break;
}
}
return slow;
}
- 判断一个链表是否带环，若带返回环的入口点（较难）
上面已经说过，通过快慢指针可以找到单链表中的任何节点，这也是通过验证的。那么原理上也可以判断链表是否带环：
如果带环，快慢指针一定会在某个节点处相遇。（fast一直在环里转，总有一个时刻，slow追上fast，相遇）
1. SListNode* WhetherRing(SListNode* pHead)//判断是否带环，若带，返回相遇节点
2. {
3. if (pHead == NULL||pHead->next == NULL)
4. return NULL;
5. SListNode* fast = pHead;
6. SListNode* slow = pHead;
7. while (fast)
8. {
9. slow = slow->next;
10. fast = fast->next;
11. if (fast)
12. {
13. fast = fast->next;
14. }
15. else
16. {
17. return NULL;//没有环
18. }
19. if (fast == slow)
20. {
21. return slow;//有环
22. }
23. }
24. return NULL;
25. }
如果链表带环的话，我们就可以求出相遇的节点。然后从相遇节点处断开带环链表，一个指针从链表投节点处开始往后遍历，一个指针从断开处往后遍历，相遇节点处就是环的入口点
1. SListNode* GetEnterNode(SListNode* pHead)//找到链表环入口节点在哪（重点）
2. {
3. SListNode* start = pHead;
4. SListNode* tmp = WhetherRing(pHead);
5. while (start != tmp)
6. {
7. start = start->next;
8. tmp = tmp->next;
9. }
10. return start;
11. }
- 将单链表反转
从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O（n）。参考代码如下：
1. // 反转单链表
2. ListNode * ReverseList(ListNode * pHead)
3. {
4. // 如果链表为空或只有一个结点，无需反转，直接返回原链表头指针
5. if(pHead == NULL || pHead->m_pNext == NULL)
6. return pHead;
7.
8. ListNode * pReversedHead = NULL; // 反转后的新链表头指针，初始为NULL
9. ListNode * pCurrent = pHead;
10. while(pCurrent != NULL)
11. {
12. ListNode * pTemp = pCurrent;
13. pCurrent = pCurrent->m_pNext;
14. pTemp->m_pNext = pReversedHead; // 将当前结点摘下，插入新链表的最前端
15. pReversedHead = pTemp;
16. }
17. return pReversedHead;
18. }
- 查找单链表中的倒数第K个结点（k > 0）
最普遍的方法是，先统计单链表中结点的个数，然后再找到第（n-k）个结点。注意链表为空，k为0，k为1，k大于链表中节点个数时的情况。时间复杂度为O（n）。代码略。
这里主要讲一下另一个思路，这种思路在其他题目中也会有应用。
主要思路就是使用两个指针，先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点。
参考代码如下：
1. // 查找单链表中倒数第K个结点
2. ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // 函数名前面的R代表反向
3. {
4. if(k == 0 || pHead == NULL) // 这里k的计数是从1开始的，若k为0或链表为空返回NULL
5. return NULL;
6.
7. ListNode * pAhead = pHead;
8. ListNode * pBehind = pHead;
9. while(k > 1 && pAhead != NULL) // 前面的指针先走到正向第k个结点
10. {
11. pAhead = pAhead->m_pNext;
12. k--;
13. }
14. if(k > 1 || pAhead == NULL) // 结点个数小于k，返回NULL
15. return NULL;
16. while(pAhead->m_pNext != NULL) // 前后两个指针一起向前走，直到前面的指针指向最后一个结点
17. {
18. pBehind = pBehind->m_pNext;
19. pAhead = pAhead->m_pNext;
20. }
21. return pBehind; // 后面的指针所指结点就是倒数第k个结点
22. }
- 从尾到头打印单链表
对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。所以，这一题要么自己使用栈，要么让系统使用栈，也就是递归。注意链表为空的情况。时间复杂度为O（n）。参考代码如下：
自己使用栈：
1. // 从尾到头打印链表，使用栈
2. void RPrintList(ListNode * pHead)
3. {
4. std::stack<ListNode *> s;
5. ListNode * pNode = pHead;
6. while(pNode != NULL)
7. {
8. s.push(pNode);
9. pNode = pNode->m_pNext;
10. }
11. while(!s.empty())
12. {
13. pNode = s.top();
14. printf("%d\t", pNode->m_nKey);
15. s.pop();
16. }
17. }
使用递归函数：
1. // 从尾到头打印链表，使用递归
2. void RPrintList(ListNode * pHead)
3. {
4. if(pHead == NULL)
5. {
6. return;
7. }
8. else
9. {
10. RPrintList(pHead->m_pNext);
11. printf("%d\t", pHead->m_nKey);
12. }
13. }
- 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
这个类似归并排序。尤其注意两个链表都为空，和其中一个为空时的情况。只需要O（1）的空间。时间复杂度为O（max(len1, len2)）。参考代码如下：
1. ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)
2. {
3. if(pHead1 == NULL)
4. return pHead2;
5. if(pHead2 == NULL)
6. return pHead1;
7. ListNode * pHeadMerged = NULL;
8. if(pHead1->m_nKey < pHead2->m_nKey)
9. {
10. pHeadMerged = pHead1;
11. pHeadMerged->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);
12. }
13. else
14. {
15. pHeadMerged = pHead2;
16. pHeadMerged->m_pNext = MergeSortedList(pHead1, pHead2->m_pNext);
17. }
18. return pHeadMerged;
19. }
- 判断一个单链表中是否有环
这里也是用到两个指针。如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。时间复杂度为O（n）。参考代码如下：
1. bool HasCircle(ListNode * pHead)
2. {
3. ListNode * pFast = pHead; // 快指针每次前进两步
4. ListNode * pSlow = pHead; // 慢指针每次前进一步
5. while(pFast != NULL && pFast->m_pNext != NULL)
6. {
7. pFast = pFast->m_pNext->m_pNext;
8. pSlow = pSlow->m_pNext;
9. if(pSlow == pFast) // 相遇，存在环
10. return true;
11. }
12. return false;
13. }
- 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted
对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)。参考代码如下：
1. void Delete(ListNode * pHead, ListNode * pToBeDeleted)
2. {
3. if(pToBeDeleted == NULL)
4. return;
5. if(pToBeDeleted->m_pNext != NULL)
6. {
7. pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey; // 将下一个节点的数据复制到本节点，然后删除下一个节点
8. ListNode * temp = pToBeDeleted->m_pNext;
9. pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;
10. delete temp;
11. }
12. else // 要删除的是最后一个节点
13. {
14. if(pHead == pToBeDeleted) // 链表中只有一个节点的情况
15. {
16. pHead = NULL;
17. delete pToBeDeleted;
18. }
19. else
20. {
21. ListNode * pNode = pHead;
22. while(pNode->m_pNext != pToBeDeleted) // 找到倒数第二个节点
23. pNode = pNode->m_pNext;
24. pNode->m_pNext = NULL;
25. delete pToBeDeleted;
26. }
27. }
28. }
网友评论