链表

1.求链表节点

while遍历node->next，然后node赋值node->next

unsigned int GetListLength(ListNode * pHead)
{
    if(pHead == NULL)
        return 0;
 
    unsigned int nLength = 0;
    ListNode * pCurrent = pHead;
    while(pCurrent != NULL)
    {
        nLength++;
        pCurrent = pCurrent->m_pNext;
    }
    return nLength;
}

2.反向单链表

创建两个变量，一个表示当前列表节点，一个表示新列表节点。旧列表的下一个节点设置为设置为新列表的节点，旧列表当前节点当做新节点的下一个节点。

ListNode * ReverseList(ListNode * pHead)
{
        // 如果链表为空或只有一个结点，无需反转，直接返回原链表头指针
    if(pHead == NULL || pHead->m_pNext == NULL)  
        return pHead;
 
    ListNode * pReversedHead = NULL; // 反转后的新链表头指针，初始为NULL
    ListNode * pCurrent = pHead;
    while(pCurrent != NULL)
    {
        ListNode * pTemp = pCurrent;
        pCurrent = pCurrent->m_pNext;
        pTemp->m_pNext = pReversedHead; // 将当前结点摘下，插入新链表的最前端
        pReversedHead = pTemp;
    }
    return pReversedHead;
}

3.链表查询倒数第k个节点

设置两个指针，前者不动，后者做next赋值k次，然后开始一起执行赋值next，后一个为null时，取前一个节点

4.链表查询中间节点

两个指针，一个是另一个的赋值的两倍。

5.从尾到头打印单链表

使用数组保存。将next节点插入到第一个位置。

6.已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序

依次判断链表1的某个位置节点是否小于另一个位置的节点，分别做计算。

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.判断一个单链表中是否有环

两个指针一个是另一个两倍。如果直到结束都没有相等的则没有环。

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.判断两个单链表是否相交

对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。
对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。
两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同。
时间复杂度，O(len1+len2)。参考代码如下：

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.两个节点相交的第一个节点

先判断两个链表是否有交点。然后将长的节点移到跟短的链表一样的位置，然后一起移动，直到两个节点一样。

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;
        }   
    }
}