手写代码:一个单向链表,给出头结点,找出倒数第N个结点,要求O(N)的时间复杂度;
参考回答:
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]