Leetcode（19）-删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

思路：链表不同于数组，也不同于字符串，不可能事先知道它的长度，除非遍历到最后结尾。删除倒数第N个节点，可以先遍历到链表尾部，再反向遍历N个，找到倒数第N个节点删除就好了。但是这种方式明显太复杂了，如果我要删除第一个节点的话，那就要遍历两轮了。

所以我们可以一次遍历就找到倒数第N个节点，就是采用双指针。两个指针差N-1个节点，当快的指针到达尾部的时候，慢的指针刚好指到倒数第N个，然后删除该节点就好了，我们这里注意，删除一个节点，要使它的前面的指针指向它后面的指针，所以我们还要维护一个慢的指针前面的指针，用来完成删除操作。

另外就是在编程中要注意对特殊情况的判断，比如就一个节点，删除变为空的情况，以及删除的是头结点的情况

 ListNode* removeNthFromEnd(ListNode* head, int n)

    {

        if(head==NULL) return head;

        ListNode*p1,*p2,*p3;

        p1=p2=p3=head;

        int num=0;

        if(num==n-1 && head->next==NULL)//只有一个节点

            return NULL;

        while(p2->next)

        {

            if(num==n-1)//当快慢指针差距n-1之后，要保持住

            {

                p3=p1;

                p1=p1->next;

                num--;

            }

            p2=p2->next;

            num++;

        }

        p3->next=p1->next;

        if(p1==head)//如果要删除的节点是头结点

        {

            head=p1->next;

        }

        delete p1;

        return head;

    }

巴特西

Leetcode（19）-删除链表的倒数第N个节点

最新文章

热门文章