题目:输入一个单向链表(只有指向下一个结点指针),输出链表中的倒数第k个结点。
分析:
1. 一个单向链表只有指向下一个结点的指针,所以我们无法得到前面一个结点的指针,所以不能通过最朴素的枚举法来求出。
2. 现在要求出倒数第k个结点。现在用一个指针枚举是无法求出,但是我们可以使用两个指针法(非常重要)。
初始化设置两个指针p1和p2,p1和p2都指向链表的头结点。我们可以先让指针p1指针先走到第k个结点,下一步开始两个指针p1和p2一起走,当p1指向链表最后一个结点的时候p2指向即为倒数第k个结点。
为什么呢这个方法是正确的?
当p1指向第k个结点的时候,p2和p1相差k个结点,所以当p1指向尾结点的时候,p2指向的即为倒数第k个结点。
代码:
//链表结点 struct ListNode{ int value; ListNode *nextNode; }; //求倒数第k个结点 ListNode* GetKthFromTail(ListNode *headNode, int k){ //数据不合法 if((headNode == NULL) || (k <= 0)){ return NULL; } ListNode *p1 = headNode; ListNode *p2 = headNode; int count = 1; //让p1先走到第k个结点 while((count < k) && (p1 != NULL)){ p1 = p1->nextNode; ++count; } //判断数据合法性 if(p1 == NULL){ return NULL; } //两个指针一起走,当p1指向尾结点是p2指向即为倒数第k个结点 while(((p1->nextNode) != NULL)){ p1 = p1->nextNode; p2 = p2->nextNode; } return p2; }
时间: 2024-12-30 16:52:24