博文中会简要介绍Leetcode P0019题目分析及解题思路。
“Remove Nth Node From End of List”是一道很经典的双指针的问题，这道题的考察重点是双指针问题的一个分支，即快慢指针。
Given a linked list, remove the n-th node from the end of list and return its head.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
这道题实现O(n)时间复杂度的解法主要有两种，一种是用空间换时间，即每个遍历过的结点存储在数组中，这样以O(n)的空间复杂度换取O(n)的时间复杂度；另一种就是使用快慢指针，使得空间复杂度也是O(1)。
核心思路就是控制快慢指针之间的间隔。这题是需要找到倒数第n个结点，则应当想到当快指针走到末尾的时候，慢指针恰好离快指针n个结点，此时慢指针指向的便是倒数第n个结点。
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null)
return head;
ListNode dummy = new ListNode(0, head);
ListNode slow = head, fast = head, prevSlow = dummy;
for (int counter=0; counter<n; ++counter)
fast = fast.next;
while (fast != null) {
slow = slow.next;
prevSlow = prevSlow.next;
fast = fast.next;
}
prevSlow.next = slow.next;
return dummy.next;
}
}
以下是C++的题解代码实现。
/**
* 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) {
if (head == NULL)
return head;
ListNode *dummy = new ListNode(0, head);
ListNode *slow = head, *fast = head, *prev_slow = dummy;
for (int counter=0; counter<n; ++counter)
fast = fast->next;
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
prev_slow = prev_slow->next;
}
prev_slow->next = slow->next;
delete slow;
slow = NULL;
return dummy->next;
}
};