删除链表的倒数第N个节点

佚名 5年前 (2020-02-27) 算法 713人围观抢沙发百度已收录

题意：

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

示例：

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

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

说明：

给定的 n 保证是有效的。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

算法：

定义两个指针fast，slow，其中fast指针先走n步，因为题目保证给定的n是有效的，所以如果fast走n步后值为NULL，则删除头结点；

否则两个指针开始一起走，直到fast指向链表最后一个节点，此时slow所指节点为应该删除节点的前一个节点。

代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* removeNthFromEnd(ListNode* head, int n) {
12         ListNode *fast = head;
13         ListNode *slow = head;
14         ListNode *temp = NULL;
15         while (n--)
16             fast = fast->next;
17         if (fast == NULL)
18         {
19             temp = head->next;
20             delete head;
21             return temp;
22         }
23         while (fast->next != NULL)
24         {
25             fast = fast->next;
26             slow = slow->next;
27         }
28         temp = slow->next;
29         slow->next = temp->next;
30         delete temp;
31         return head;
32     }
33 };