首页 > 代码库 > 剑指offer (15) 链表倒数第K个结点

剑指offer (15) 链表倒数第K个结点

题目:

输入一个链表,输出该链表中倒数第k个结点 (注意:我们将链表最末一个结点记为 倒数第1个结点,也就是k从1开始计数)

解题分析:

方法一:遍历链表两次,第一次统计链表结点个数,第二次遍历就可以找到倒数第K个结点

方法二:遍历链表一次

我们使用两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针一直指向链表开头并保持不动

从第k步开始,两个指针同时向前走,这时 两个指针之间的距离一直是k-1

当第一个指针到达链表尾结点时,第二个指针指向链表倒数第k个结点

  

 

 1 ListNode* FindKthNode(ListNode* pListHead, int k)
 2 {
 3     assert(pListHead != NULL && k > 0);
 4     ListNode* prev = pListHead;
 5     ListNode* last = pListHead;
 6     int steps = 0;
 7     while (prev != NULL && steps < k - 1) {
 8         prev = prev->next;
 9         ++steps;
10     }
11     if (prev == NULL) return NULL;
12     while (prev != NULL) {
13         prev = prev->next;
14         last = last->next;
15     }
16     return last;
17 }

需要注意以下几点:

1. k >= 1,需要对 k的输入做检查

2. 对函数的输入指针必须做空指针判断

3. 注意 k 大于 链表结点个数的情况,因此 在 while循环中 prev != NULL 

 

扩展:

1. 求链表的中间结点,只允许遍历一次.  思路完全相同,定义两个指针同时从头结点出发,前面一个指针每次走2步,后面一个指针每次走1步

2. 判断单链表是否存在环. 我们也是定义两个指针,两指针同时从 头结点出发,前面一个指针每次走2步,后面一个指针每次走1步

如果前面的指针追到了 后面的指针,那么就存在环,如果 前面的指针一直走到链表末尾都没有追到,那么就不存在环

注:其实这个就可以想象成两个人在环形操场上跑步,如果跑得快的人 追上了 跑得慢的人,就多跑了一圈(即有环)