단방향 연결리스트가 있을 때, 맨 뒤에서 k번 째 원소 구하기

두 개의 포인터 p1과 p2를 사용한다.

p2는 연결리스트의 시작 노드를 가리키고,

p1은 k 노드만큼 움직여서

p1과 p2가 k 노드만큼 떨어져 있도록 만드는 것이다.

그런 다음 p1과 p2를 같이 동시에 함께 이동시키면

p1은 Length - k 번 후에 연결리스트이 맨 마지막 노드에 도달할 것이다.

즉, p2는 Length - k번 째 노드, 그러니까 뒤에서부터 k 번 째 노드를 가리키게 된다.

LinkedListNode nthToLast(LinkedListNode head, int k)
{
    LinkedListNode p1 = head;
    LinkedListNode p2 = head;
    // p1을 k 노드만큼 이동시킨다.
    for (int i = 0; i < k; i++)
    {
        if (p1 == NULL) return NULL; // Out of bounds
        p1 = p1.next;
    }
    /*
    p1과 p2를 함께 움직인다.
    p1이 끝에 도달하면, p2는 Length - k 번 째 원소를 가리키게 된다.
    */
    while (p1 != NULL)
    {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}