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;
    }

Posted by richard爱闹 - 7月 29 2014
如需转载,请注明: 本文来自 Richard