首页 > 代码库 > 链表中倒数第K个结点

链表中倒数第K个结点

题目:
输入一个链表,输出该链表中倒数第K个结点。为了符合大多数人的习惯,从1开始计数,即链表的尾结点是倒数第1个结点。

例如一个链表有6个结点,从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第2个结点是值为5的结点。

思路:
1.最直观的想法,就是先算出链表的长度n,然后倒数第k个结点就是顺序的第(n-k+1)个数,不过这样需要2次遍历链表,
如果要求只能遍历链表一次,那么上述算法就不符合要求了。

2.那我们就使用第二种算法,设定两个指针p1和p2,两个指针刚开始都指向链表的第一个结点,然后让p1指针先走(k-1)步,
然后再让两个指针一起往后走,当p1指针指向链表最后一个结点的时候,p2指针刚好指向链表中的倒数第k个结点。

在写代码的时候需要考虑鲁棒性,因此要考虑在哪些地方会出错,然后提前加上判断,从而避免因非法输入而导致程序崩溃。


代码如下:
 1 ListNode* KthNodeFromEnd(ListNode* pHead, int k)
 2 {
 3     if(pHead==NULL || k<=0)
 4     {
 5         return NULL;
 6     }
 7     
 8     ListNode* pNode = pHead;
 9     ListNode* pKthNode = pHead;
10     
11     while(k-1 > 0)
12     {
13         if(pNode->m_pNext != NULL)
14         {
15             pNode = pNode->m_pNext;//让pNode先走k-1步
16             k--;
17         }
18         else
19         {
20             return NULL;
21         }
22     }
23     
24     while(pNode->m_pNext != NULL)
25     {
26         pNode = pNode->m_pNext;
27         pKthNode = pKthNode->m_pNext;
28     }
29     
30     return pKthNode;
31 }