关于链表算法题的双指针

今天药忘吃喽~ 2022-02-01 22:41 206阅读 0赞

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

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

1、 判定链表中是否环

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

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

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

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

bool judge(list *head)
    {
        if(head == NULL)
        {
            return false;//没有环
        }
    
        list *pFast = head;
        list *pSlow = head;
    
        while(pFast->next != NULL && pFast->next->next != NULL)
        {
            pFast = pFast->next->next;
            pSlow = pSlow->next;
    
            if(pFast == pSlow)
            {
                return true;
            }
        }
    
        return false;
    }

2、找到链表的中间节点

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

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

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

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

//注意程序鲁棒性，输入参数检查，元素个数不足检查。
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
    {
        if(pListHead == NULL || k == 0)
            return NULL;                        //考虑参数异常
    
        ListNode *pAhead = pListHead;
        ListNode *pBehind = NULL;
    
        for(unsigned int i = 0; i < k - 1; ++ i)
        {
            if(pAhead->m_pNext != NULL)
                pAhead = pAhead->m_pNext;
            else                               //要考虑到链表的元素不足K个的情况
            {
                return NULL;
            }
        }
    
        pBehind = pListHead;
        while(pAhead->m_pNext != NULL)
        {
            pAhead = pAhead->m_pNext;
            pBehind = pBehind->m_pNext;
        }
    
        return pBehind;
    }

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

unsigned int GetListLength(ListNode* pHead)
    {
        unsigned int nLength = 0;
        ListNode* pNode = pHead;
        while(pNode != NULL)
        {
            ++ nLength;
            pNode = pNode->m_pNext;
        }
    	
        return nLength;
    }
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
    {
        // 得到两个链表的长度
        unsigned int nLength1 = GetListLength(pHead1);
        unsigned int nLength2 = GetListLength(pHead2);
        int nLengthDif = nLength1 - nLength2;
     
        ListNode* pListHeadLong = pHead1;
        ListNode* pListHeadShort = pHead2;
        if(nLength2 > nLength1)
        {
            pListHeadLong = pHead2;
            pListHeadShort = pHead1;
            nLengthDif = nLength2 - nLength1;
        }
     
        // 先在长链表上走几步，再同时在两个链表上遍历
        for(int i = 0; i < nLengthDif; ++ i)
            pListHeadLong = pListHeadLong->m_pNext;
     
        while((pListHeadLong != NULL) && 
            (pListHeadShort != NULL) &&
            (pListHeadLong != pListHeadShort))
        {
            pListHeadLong = pListHeadLong->m_pNext;
            pListHeadShort = pListHeadShort->m_pNext;
        }
     
        // 得到第一个公共结点
        ListNode* pFisrtCommonNode = pListHeadLong;
     
        return pFisrtCommonNode;
    }

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