手写代码：一个单向链表，给出头结点，找出倒数第N个结点，要求O（N）的时间复杂度?

Answer 1

参考回答：

JAVA版本：

public class Solution {
public ListNode FindNthToTail(ListNode head,int N) {
ListNode pre=null,p=null;
//两个指针都指向头结点
p=head;
pre=head;

//记录N值
int a=N;

//记录节点的个数
int count=0;

//p指针先跑，并且记录节点数，当p指针跑了N-1个节点后，pre指针开始跑，
//当p指针跑到最后时，pre所指指针就是倒数第N个节点
while(p!=null){
p=p.next;
count++;
if(N<1){
pre=pre.next;
}
N--;
}

//如果节点个数小于所求的倒数第N个节点，则返回空
if(count<a) return null;
return pre;
}
}

 

C/C++版本：

class Solution {
public:
ListNode* FindNthToTail(ListNode* pListHead, unsigned int N) {
if(pListHead==NULL||N==0)
return NULL;
ListNode*pTail=pListHead,*pHead=pListHead;
for(int i=1;i<N;++i)
{
if(pHead->next!=NULL)
pHead=pHead->next;
else
return NULL;
}
while(pHead->next!=NULL)
{
pHead=pHead->next;
pTail=pTail->next;
}
return pTail;
}
};
Python：
class Solution:
def FindNthToTail(self, head, N):
# write code here
res=[]
while head:
res.append(head)
head=head.next
if N>len(res) or N<1:
return
return res[-N]