链表

1.两个链表的第一个公共结点

解法：若两个链表有公共结点，则公共结点出现在尾部，呈“Y”形状。因此，首先遍历两个链表得到长度；然后让较长的链表先走几步，保持两个链表同步；最后，同时遍历两个链表，找到第一个相同的结点。

typedef struct
{
    int key;
    ListNode* next;
}ListNode;

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

ListNode* FindFirstNode(ListNode* pH1,ListNode* pH2)
{
    unsigned int length1 = GetListLength(pH1);
    unsigned int length2 = GetListLength(pH2);
    
    ListNode *pLong  = pH1;
    ListNode *pShort = pH2;
    unsigned int lengthDiff = length1 - length2;
    if (length1 < length2)
    {
        lengthDiff = length2 - length1;
        pLong  = pH2;
        pShort = pH1;
    }

    for (int i = 0; i < lengthDiff; i++)//长链表先走，保持两个链表同步
    {
        pLong = pLong->next;
    }

    while ((pLong != NULL)&&(pShort != NULL)
        &&(pLong != pShort))
    {
        pLong = pLong->next;
        pShort = pShort->next;
    }

    return pLong;//若无公共结点，则返回值为NULL
}

2.链表反转

解法：首先考虑测试用例，如输入的链表头为NULL或者整个链表只有一个结点；链表有多个结点；反转之后是否会出现链表的断裂；反转后的链表不会形成循环

ListNode* ReverseList(ListNode* pHead)
{
    ListNode* pReverseHead = NULL;//指向反转后的链表头部
    ListNode* pNode = pHead;//指向原链表
    ListNode* pPre = NULL;//指向反转后的链表

    while (pNode != NULL)
    {
        ListNode* pNext = pNode->next;
        if (NULL == pNext)
            pReverseHead = pNode;

        pNode->next = pPre;
        pPre = pNode;
        pNode = pNext;
    }

    return pReverseHead;
}

持续更新中。。。