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

描述

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

思路1:遍历

先遍历一遍链表，获得结点总数sum。然后需要删除的位置就是sum-n+1（假设从1开始计数）。设置一个哨兵结点，指向head结点，因为会有删除head结点的情况。结果如下：

解答1

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {   public:    ListNode* removeNthFromEnd(ListNode* head, int n) {           ListNode* headNode = new ListNode(0, head);//哨兵结点：headNode        ListNode* p = headNode;        int sum = -1;//sum为结点总数        while(p){               sum ++;            p = p->next;        }        int index = sum-n+1;//要删除的位置        p = headNode;//p重新指向哨兵结点        int i = 0;        while(p){               if(i+1 == index){                    p->next = p->next->next;                 break;            }            i++;            p = p->next;        }        return headNode->next;    }};

思路2:双指针

即题目进阶描述的：遍历一次链表。

设置哨兵结点指向head，然后设置两个指针first和second，分别指向head结点和哨兵结点。首先让first向前移动n个位置，然后同时移动双指针，当first指针到达最后的空指针时停止移动，此时second指向的刚好是需要删除结点的前驱结点，更改其指向即可。

注：没有做哨兵结点的回收。

解答2

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {   public:    ListNode* removeNthFromEnd(ListNode* head, int n) {           ListNode* headNode = new ListNode(0, head);//哨兵结点：headNode        ListNode* first = head, * second = headNode;        for(int i=0; i
   
    next;        }        while(first){               first = first->next;            second = second->next;        }        second->next = second->next->next;        return headNode->next;    }};
   

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