链表中倒数第K个结点 牛客网 程序员面试金典 C++ Python
- 题目描述
- 输入一个链表，输出该链表中倒数第k个结点。
C++
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
//run:3ms memory:476k
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(NULL == pListHead) return NULL;
if(0 == k) return NULL;
ListNode* p = pListHead;
ListNode* res = pListHead;
for(unsigned int i = 0; i< k; i++)
if (p) p=p->next;
else return NULL;
for(;p;p=p->next)
res = res->next;
return res;
} ListNode* FindKthToTail2(ListNode* pListHead, unsigned int k) {
if(NULL == pListHead) return NULL;
if(0 == k) return NULL;
ListNode* p = pListHead;
ListNode* res = pListHead;
for(unsigned int i = 0; i< k; i++)
if (p) p=p->next;
else return NULL;
while(p) {
res = res->next;
p = p->next;
}
return res;
}
};Python
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:
#run:33ms memory:5728k
def FindKthToTail2(self, head, k):
if k<=0 or head == None:
return None
p = head
ret = head
for i in range(k):
if p:p = p.next
else:return None
while(p):
p = p.next
ret = ret.next
return ret #run:22ms memory:5852k
def FindKthToTail(self, head, k):
if k<=0 or head == None:
return None
else:
count = 0
p = head
ret = head
while p!=None:
count = count + 1
if count > k:
ret=ret.next
p = p.next
if count < k:
ret = None
return ret
