题目描述
输出单链表的倒数第K个节点的值
注意:
k >= 1;
如果 k 大于链表长度,则返回 NULL;
数据范围
链表长度 [0,30]。
输入样例
链表:1->2->3->4->5 ,k=2
输出样例
4
思路1:
- 设置两个指针,初始都指向第一个元素
- 先将第一个指针移动K个位置
- 当第一个指针移动k个位置之后,在同时移动第一和第二个指针,直到第一个指针到达表尾,此时第二个指针所指的结点就是答案
优点:此时只需要遍历一次链表即可,较快。
C语言代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* Note: The returned array must be malloced, assume caller calls free().
*/
typedef struct ListNode LNode;
struct ListNode* findKthToTail(struct ListNode* pListHead, int k) {
if(!pListHead) return NULL;//如果链表为空直接返回NULL
LNode *p1 = pListHead,*p2 = pListHead;//设置两个指针
//1.先将第一个指针移动k个位置(注意结点号是从1开始)
while(--k){
if(!p1->next) return NULL;//表明k的长度超过了链表的长度
p1 = p1->next;
}
//2.当第一个指针移动k个位置之后,接下来就同时移动第一和第二个指针
//当第一个指针到最后一个结点时,第二个指针指向的元素就是倒数第k个结点。
while(p1->next){
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
思路2:
先将链表反转,之后直接输出第K个结点即可
缺陷:会导致扫描2次链表,不够快
C代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* Note: The returned array must be malloced, assume caller calls free().
*/
struct ListNode* findKthToTail(struct ListNode* pListHead, int k) {
if(!pListHead) return NULL;//如果链表为空直接返回NULL
//先将链表反转(头插法)
struct ListNode *reversList = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *tempList = reversList;
//用头插法反转链表
int i = 1;//用来记录链表长度
while(pListHead){
struct ListNode *reversNode = (struct ListNode *)malloc(sizeof(struct ListNode));
reversNode->val = pListHead->val;
reversNode->next = tempList->next;
tempList->next = reversNode;
pListHead = pListHead->next;
i++;
}
if(i < k) return NULL;//如果输入的K大于链表长度直接返回null
i = 1;
reversList = reversList->next;//指向第一个元素
while( i != k){
reversList = reversList->next;
i++;
}
return reversList;
}