当前位置:   article > 正文

关于链表算法题的双指针_链表算法 一般都是双指针解决嘛

链表算法 一般都是双指针解决嘛

       经常能够碰到链表的题,当用一个指针遍历来解决问题的时候,不是无法解决就是效率不佳,典型的就是需要多次遍历且需要额外的存储空间。在这种情况下,可以尝试用两个指针来遍历链表,而两指针遍历链表又可以分为两种情况:1、让其中一个指针遍历快一点,比如一次在链表中走上两步;2、让其中一个指针现在链表中走上若干步。

       这里举三个链表相关的题目。

1、 判定链表中是否环

       第一种方法:可以对链表的元素进行标记,如果在预见NULL节点之前再次碰见已标记节点就存在环。缺点:需要改变节点内容,而节点一般是只读的。

       第二种方法:访问每一个元素将其存储在数组中,这个时候存储的元素是什么,如果链表中的元素有重复的值,难道存储节点地址?并且开辟了O(n)的额外空间,如果内存不够呢?

       第三种方法:如果假定链表存在环,那么环在前N个元素之中,此时可以设置一个指针指向链表的头部,然后遍历后N-1个元素,看是否是指针所指元素,如果都不同,指针指向后一个元素,然后遍历后N-2个元素。缺点:这个算法复杂度为O(n^2),而且建立在一个前提条件之下。

       最优的答案:设置两个指针,开始都指向链表头,然后其中一个指针每次向前走一步,另一个指针每次向前走两步,如果快的遇到NULL了,证明该链表中没有环,如果有环,快的指针每次都要比慢的多走一步,最终两个指针会相遇,(注意:这里快指针不会跳过慢指针而不相遇,因为它每次都只比慢指针多走一个单位)

  1. bool judge(list *head)
  2. {
  3. if(head == NULL)
  4. {
  5. return false;//没有环
  6. }
  7. list *pFast = head;
  8. list *pSlow = head;
  9. while(pFast->next != NULL && pFast->next->next != NULL)
  10. {
  11. pFast = pFast->next->next;
  12. pSlow = pSlow->next;
  13. if(pFast == pSlow)
  14. {
  15. return true;
  16. }
  17. }
  18. return false;
  19. }

2、找到链表的中间节点

       受上一题的启发可以运用两个速度不同的指针来解决,快指针每次走两步,慢指针每次走一步,这样当快指针到达链表尾部的时候,慢指针就指向了链表的中间节点。

3、 输出链表中倒数第K个数

第一种方法:单个指针遍历两次,首先遍历一次链表统计总元素个数N,那么所要找的倒数第K个元素即为第N-K+1个元素。

第二种方法:双指针遍历一次,首先前指针先向前走K-1步,即初始的时候前指针指向第K个元素,然后后指针指向第一个元素,然后同步向后单步走,当后指针指向NULL的时候,前指针指向倒数第K个元素。

  1. //注意程序鲁棒性,输入参数检查,元素个数不足检查。
  2. ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
  3. {
  4. if(pListHead == NULL || k == 0)
  5. return NULL; //考虑参数异常
  6. ListNode *pAhead = pListHead;
  7. ListNode *pBehind = NULL;
  8. for(unsigned int i = 0; i < k - 1; ++ i)
  9. {
  10. if(pAhead->m_pNext != NULL)
  11. pAhead = pAhead->m_pNext;
  12. else //要考虑到链表的元素不足K个的情况
  13. {
  14. return NULL;
  15. }
  16. }
  17. pBehind = pListHead;
  18. while(pAhead->m_pNext != NULL)
  19. {
  20. pAhead = pAhead->m_pNext;
  21. pBehind = pBehind->m_pNext;
  22. }
  23. return pBehind;
  24. }

4、 两链表的第一个公共结点——输入两个链表,找出它们的第一个公共结点。

  1. unsigned int GetListLength(ListNode* pHead)
  2. {
  3. unsigned int nLength = 0;
  4. ListNode* pNode = pHead;
  5. while(pNode != NULL)
  6. {
  7. ++ nLength;
  8. pNode = pNode->m_pNext;
  9. }
  10. return nLength;
  11. }
  12. ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
  13. {
  14. // 得到两个链表的长度
  15. unsigned int nLength1 = GetListLength(pHead1);
  16. unsigned int nLength2 = GetListLength(pHead2);
  17. int nLengthDif = nLength1 - nLength2;
  18. ListNode* pListHeadLong = pHead1;
  19. ListNode* pListHeadShort = pHead2;
  20. if(nLength2 > nLength1)
  21. {
  22. pListHeadLong = pHead2;
  23. pListHeadShort = pHead1;
  24. nLengthDif = nLength2 - nLength1;
  25. }
  26. // 先在长链表上走几步,再同时在两个链表上遍历
  27. for(int i = 0; i < nLengthDif; ++ i)
  28. pListHeadLong = pListHeadLong->m_pNext;
  29. while((pListHeadLong != NULL) &&
  30. (pListHeadShort != NULL) &&
  31. (pListHeadLong != pListHeadShort))
  32. {
  33. pListHeadLong = pListHeadLong->m_pNext;
  34. pListHeadShort = pListHeadShort->m_pNext;
  35. }
  36. // 得到第一个公共结点
  37. ListNode* pFisrtCommonNode = pListHeadLong;
  38. return pFisrtCommonNode;
  39. }

        顺便说一句,单链表翻转的算法运用了3指针,这是为了记录前后节点。



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/956940
推荐阅读
相关标签
  

闽ICP备14008679号