Remove Nth Node from end of List
由于题目对于n给了约束,一定是合法的,所以1<=n<=length(Linklist),
如果长度为0的话,n也不存在,不过还是判断下链表为空的情况。
模仿找倒数第n个结点,其实和两遍遍历操作次数没太大差别,只是说方法比较巧,用两个指针同步走。
由于需要删掉倒数第n个结点,实际是找倒数第n+1个结点,所以后指针要向后移n+1次,我已开始移了n次,然后后面
判断循环结束是找到尾结点就结束,而不是到NULL,其实是一样的,但是用p->next==NULL要多一步检查p是否空这么一步越界判断。
这里边界主要就是判断n=length(Linklist)这种情况,因为找到倒数第n个就是head,那倒数n+1不在链表里,所以直接
head=head->next就可以了。
ListNode *removeNthFromEnd(ListNode *head, int n) {
if(head==NULL) return NULL;
ListNode*p=head;
int i=1;
while(i<=n)
{
p=p->next;
i++;
}
ListNode* pprev=head;
if(p==NULL)//length==n
{
head=head->next;
return head;
}
while(p->next!=NULL)//length>n>=1
pprev=pprev->next,p=p->next;
pprev->next=pprev->next->next;
return head;
}
如果选择后移n+1位,就要考虑了,因为while循环要保证n+1<=length(Linklist), 当n==length(Linklist),可能p到了NULL还要next,这个时候可以确定需要
倒数第n个结点,也即head,所以直接head=head->next就可以了,这个case提到前面找p的时候来处理掉
ListNode *removeNthFromEnd(ListNode *head, int n) {
if(head==NULL) return NULL;
ListNode*p=head;
int i=1;
while(i<=n+1)
{
if(p==NULL) {head=head->next;return head;}//length==n
p=p->next;
i++;
}
ListNode* pprev=head;
while(p!=NULL)//length>n>=1
pprev=pprev->next,p=p->next;
pprev->next=pprev->next->next;
return head;
}