【剑指offer】22.链表的倒数第K个节点
java:
遍历的时候就在记录次数。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode p = head;
ListNode q = head;
int i =0;
for(;p!=null;i++){
if(i>=k)
q=q.next;
p=p.next;
}
return i < k ? null : q;
}
}
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k<=0)
return null;
ListNode p = head;
ListNode q = head;
for(int i =1;i<k;i++){
if( p.next!=null)
p=p.next;
else
return null;
}
while(p.next!=null){
p=p.next;
q=q.next;
}
return q;
}
}
C++:
遍历一次 循环一次
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* head, int k) {
int n=0;
for(auto p=head;p;p=p->next) n++;
if(n<k)
return NULL;
auto p = head;
for(int i=0;i<n-k;i++)
p=p->next;
return p;
}
}