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

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

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

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

思路

本题思路有二：

第一种：

自己的做法。

  • 使用虚拟头节点对链表进行反转操作
  • 用cnt从前遍历n个，然后删除该节点
  • 再次使用虚拟头节点对链表进行反转

第二种：

双指针、虚拟头节点法做。

为什么要用虚拟头节点的方法做？

因为用虚拟头节点做的话可以不用考虑删除的元素是否为头节点。虚拟头节点一直指向的是链表的头节点的位置，就算链表的头结点变了，虚拟头节点还是可以link到新的头节点的位置。

  • 使用一个快指针前进n+1个节点
  • 快、慢指针同时向前走，直到快指针遍历结束
  • 此时慢指针指向n-1元素的位置，直接删除第n个元素即可

以下c语言的做法就是用的第一种方法做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    typedef struct ListNode ListNode;
    ListNode* pre = NULL;
    ListNode* cur = head;
    ListNode* temp = NULL;
    while(cur){
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    int cout =1;
    ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    phead->next = pre;
    cur = phead;
    while(cur->next){
        if(cout == n){
            cur->next = cur->next->next;
            break;
        }else{
        cout++;
        cur = cur->next;}
    }
    pre = NULL;
    cur = phead->next;
    while(cur){
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

以下c++代码实现第二种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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* phead = new ListNode;
        phead->next = head;
        ListNode* fast = phead;
        ListNode* low = phead;
        while(n-- && fast->next){
            fast = fast->next;
        }
        fast = fast->next;
        while(fast){
            fast = fast->next;
            low = low->next;
        }
        ListNode* temp = low->next;
        low->next = low->next->next;
        delete temp;
        return phead->next;
    }
};