本来以为一篇就能写完的，后来又感觉一篇多了一些，所以关于链表的简单算法题有加了个续篇，和上一篇一样，难度不会太大。

• 链表中倒数第k个结点
• 合并两个排序的链表
• 找到两个链表中的第一个公共结点

1.链表中的倒数第k个结点

问题描述：输入一个链表，计算链表中的倒数第k个结点(从1开始计数)。

算法思想

我们可以分析链表结点个数n和倒数第k个结点之间的关系，如果链表有n个结点，那么它的倒数第k个结点也就是链表顺着数的第n-k+1个结点。
思路一：先遍历链表，得到结点个数n，再遍历链表，找到第n-k+1个结点。这一种思路需要两次遍历链表，时间复杂度为O(n)。
思路二：能不能一次遍历就找到结点呢？这就是接下来要说的了。我们可以使用两个指针，第一个指针从头结点开始，向前走k-1步，然后第二个指针指向首结点，接下来两个指针顺序后移，当第一个指针指向最后一个结点的时候，第二个指针刚好指向倒数第k个几点。两个指针之间间隔为k-1。

代码：

算法思想清楚了之后，代码就简单多了。写出代码之后，我们需要关注其鲁棒性，针对特殊的输入，代码能否完成任务。这些都是代码中需要考虑到的。
特殊输入：
1.如果pHead为NULL，那么不存在倒数第K个结点，应该返回NULL。
2.k接收的无符号数，如果输入k=0,因为k是无符号数，for循环k-1次的时候,得到的将不会是-1，而是一个非常大的数字，for循环的次数会超过我们的预期。
3.如果输入的k大于链表结点总数，那么在for循环遍历链表的时候，会出现指向NULL的指针。

链表的数据结构定义：

typedef struct ListNode *list_pointer;
typedef struct ListNode
{
    int value;
    list_pointer link;
};
list_pointer pHead;

查找链表中的倒数第k个结点（从1开始计数）。

list_pointer FindKthNodeFromEnd(list_pointer pHead, unsigned int k)
{
    //链表中的结点计数从1开始，所以不存在倒数第0个结点
    if (pHead == NULL || k == 0) {
        return NULL;
    }
    list_pointer pAhead = pHead;
    list_pointer pBehind;

    for (int i = 0; i < k - 1; i++)
    {
        if (pAhead->link)//防止k大于链表结点个数的情况发生
        {
            pAhead = pAhead->link;
        }
        else
        {
            fprintf(stderr, "K is bigger than length of linklist\n");
            exit(1);
        }
    }

    pBehind = pHead;
    while (pAhead->link)//判断pAhead是不是指向最后一个结点
    {
        pAhead = pAhead->link;
        pBehind = pBehind->link;
    }
    return pBehind;
}

相关题目

类似的题目还有很多，我们可以借助两个指针，很快的得到结果。
题目一：求链表的中间结点，如果链表结点数为奇数，则输出中间结点，如果链表结点数为偶数， 则输出中间两个中的一个。
算法思想：定义两个指针，一个指针一次走一步，另一个指针一次走两步，当走得快的指针到达链表尾是，走得慢的刚好指向链表中间结点。
题目二：判断一个单向链表是否是环形链表。
算法思想：定义两个指针，从首结点开始，一个指针一次走一步，另一个指针一次走两步，如果走的快的指针追到了走得慢的指针，那么这个链表就是环形的，如果走的快的指针走到了链表的末尾都没有追到慢的指针，那么就不是环形链表。

代码

这里写了题目一的代码，可以参考一下。需要注意的代码中的while的循环条件，判断了pAhead和pAhead->link，这里是判断是否指向了尾节点，如果链表结点数为偶数，是用pAhead==NULL来判断是否到尾节点的；如果链表有奇数个结点，就是用pAhead->link==NULL来判断的。

//找中间结点
list_pointer getTheMiddleNode(list_pointer pHead)
{
    if (pHead == NULL){
        fprintf(stderr, "the linklist is empty.\n" );
        exit(1);
    }
    if (pHead->link == NULL)//如果链表中只有一个结点，那么中间结点就是该结点
        return pHead;
    list_pointer pAhead = pHead, pBehind = pHead;
    //如果走的快的指针没有指向尾结点
    while (pAhead && pAhead->link)
    {
        pAhead = pAhead->link->link;
        pBehind = pBehind->link;
    }
    return pBehind;
}

2.合并两个排序的链表

问题描述：输入两个排好序的链表，合并两个链表，并返回合并后的链表的头结点。

算法思想

用两个指针，一个指向a链表的结点，一个指向b链表的结点。都从链表头开始，依次比较。针对两个链表中的第一个结点，比较大小，小的结点加到合并的之后的链表中，然后加入合并链表的那个链表指针后移，然后计算省下结点的的头结点，接下来将计算出来的结点接到合并链表的链表尾，剩余的结点也是这样处理。这样分析下来，就是典型的递归了。使用递归，我们可以很快的解决这道题。

代码

//合并两个排好序的链表,用递归，每次都比较链表中剩余结点的头结点
list_pointer Merge(list_pointer pHead1, list_pointer pHead2)
{
    if (pHead1 == NULL)
        return pHead2;
    if (pHead2 == NULL)
        return pHead1;

    list_pointer pMerge = NULL;//合并之后的链表的头结点
    //每次都比较链表中剩余结点的头指针
    if (pHead1->value < pHead2->value)
    {
        pMerge = pHead1;
        pMerge->link = Merge(pHead1->link, pHead2);
    }
    else
    {
        pMerge = pHead2;
        pMerge->link = Merge(pHead1, pHead2->link);//接到上一个结点后面
    }
    return pMerge;
}

3.找到两个链表中的第一个公共结点

问题描述：输入两个链表，计算两个链表的公共结点。

算法思想

思路一：蛮力法，遍历第一个链表，每遍历一个结点时，在第二个链表上顺序遍历所有结点，如果第二个链表上有结点和第一个链表的结点相等，那么就找到了公共结点。这种思路的时间复杂度是O(n^2)，效率很低。
思路二：首先分析有公共结点的两个链表的特点，如果两个链表存在公共结点，那么两个链表都一定存在一个结点，它的link指向相同。单向链表的每个结点只能有一个指向，所以从第一个公共结点开始，之后它们的所有结点都是重合的，不可能再分叉。所以两个有公共结点而部分重合的链表，看起来像Y。

首先，可以确定，如果两个链表有公共结点，那么公共结点一定是在链表尾部。如果从两个链表的最后一个结点开始比较，遇到最后一个相等的结点就是它们的公共结点了。但是链表要定位到最后一个结点就需要从头遍历，最先遍历到的结点最后比较，最后遍历到的结点(尾结点)第一个比较，所以我们可以使用栈。先遍历两个链表，用两个栈来存储每个结点。每次比较栈顶结点，直到比较到最后一个相等的结点。时间复杂度O(m+m)，m,n分别是两个链表的长度，空间复杂度也是O(m+n)。

思路三：用栈的目的就是定位到最后一个元素，方便从后往前遍历。这样就解决了两个链表的结点数不一致时，到达尾结点的时间不同。换一种思路。如果提前知道链表长度，我们就可以知道长的链表比短的链表多几个元素，那么长的链表先走几步，然后两个链表开始同时向后遍历，遇到的第一个相同的结点就是其公共结点了。这种思想的时间复杂度是O(m+n)，但是我们不再需要额外的空间辅助了。

代码

思路三代码。

//计算链表长度
unsigned int getLength(list_pointer p)
{
    list_pointer pNode = p;
    int length = 0;
    while (pNode)
    {
        length++;
        pNode = pNode->link;
    }
    return length;
}

//计算两个链表的第一个公共结点
ListNode* FindFirstCommonNode(list_pointer pHead1, list_pointer pHead2)
{
    if (!pHead1 || !pHead2)
        return NULL;
    //得到两个链表的长度
    unsigned int nLength1 = getLength(pHead1);
    unsigned int nLength2 = getLength(pHead2);

    int nLengthDif = nLength1 - nLength2;
    list_pointer pListHeadLong = pHead1;
    list_pointer pListHeadShort = pHead2;

    if (nLength1 < nLength2)
    {
        nLengthDif = nLength2 - nLength1;
        pListHeadLong = pHead2;
        pListHeadShort = pHead1;
    }

    //长的链表先走
    for (int i = 0; i < nLengthDif; i++)
    {
        pListHeadLong = pListHeadLong->link;
    }

    while (pListHeadLong && pListHeadShort
        && pListHeadLong != pListHeadShort)
    {
        pListHeadLong = pListHeadLong->link;
        pListHeadShort = pListHeadShort->link;
    }
    //得到第一个公共结点
    ListNode *theCommonNode = pListHeadLong;
    return theCommonNode;
}

总结

遇到这些问题的时候，常规思路的解决方法我们的通常都能想到，但是时空效率很低，看到这些高效的解决方法的时候，我觉得真是很奇妙，快捷方便的解决了问题。我们可以从这些方法之中学习一种思路，比如说一个指针解决不了的，试试两个指针，总结要解决的问题和链表特有的存储结构的关系等。这次就到这里了，不足之处，请多指教~