本文共 1591 字，大约阅读时间需要 5 分钟。

19.删除链表的倒数第n个结点

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

• 先用两趟扫描的方法，一趟扫描先知道链表长度，再遍历到指定位置进行删除。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    ListNode* removeNthFromEnd(ListNode* head, int n) {
           if(head==NULL) return head;        if(head->next==NULL) return head->next;        int length=0;        ListNode *p=head,*q=head->next;        while(p){
               length++;            p=p->next;        }        if(length == n){
               return head->next;        }        p=head;        while(length-n-1 && q->next){
               p=p->next;            q=q->next;            length--;        }        p->next=q->next;        return head;    }};

通过时间：

• 进阶：用一趟扫描完成，使用了快慢指针的方法，第一个指针先走n步，第二个指针再开始走，这样当第一个指针到链表末尾的时候，第二个指针就在倒数第n个结点上。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    ListNode* removeNthFromEnd(ListNode* head, int n) {
           if(head==NULL) return head;        if(head->next==NULL) return head->next;        ListNode *p=head,*q=head;        while(n){
               q=q->next;            n--;        }        if(q==NULL) return head->next;        while(q->next){
               p=p->next;            q=q->next;        }        p->next=p->next->next;        return head;    }};

通过时间：

转载地址：http://wiemb.baihongyu.com/