链表中倒数第k个节点

描述

输入一个链表，输出该链表中倒数第k个结点。

解析

第一种办法可以先求出链表长度，然后求正数第len+1-k个节点，但是这样浪费了时间，因为可以在一次遍历的情况下得到倒数第k个，使用两个指针p1，p2，然后让p2和p1距离为k-1，然后依次增加p1和p2，直到p2为链表最后一个节点。需要注意k<=0和链表长度不够这两种情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) 
{
    if(pListHead == NULL || k == 0)
        return NULL;
    ListNode* p1 = pListHead;
    ListNode* p2 = pListHead;
    int i = static_cast<int>(k);
    while(i - 1 > 0)
    {
    	if(p2->next != NULL)
        {
        	p2 = p2->next;
            --i;
        }
        else
        {
        	return NULL;    
        }
    }
    while(p2->next != NULL)
    {
    	p2 = p2->next;
        p1 = p1->next;
    }
    return p1;
}