博客

为了能够只遍历一次就能找到倒数第k个节点，可以定义两个指针：   （1）第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；   （2）从第k步开始，第二个指针也开始从链表的头指针开始遍历；   （3）由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。   下图展示了在有6个结点的链表上找倒数第3个结点的过程：

举一反三：

当我们用一个指针遍历链表不能解决问题的时候，

可以尝试用两个指针来遍历链表

。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。

public static Node FindKthToTail(Node head, uint k)
    {
        if(head == null || k == 0)
        {
            return null;
        }

        Node ahead = head;
        Node behind = null;

        for (int i = 0; i < k - 1; i++)
        {
            if(ahead.Next != null)
            {
                ahead = ahead.Next;
            }
            else
            {
                return null;
            }
        }

        behind = head;

        while (ahead.Next != null)
        {
            ahead = ahead.Next;
            behind = behind.Next;
        }

        return behind;
    }

原文