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

发表于 | 更新于 | 分类于

题目描述

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

1
2
3
示例：

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

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

给定的 n 保证是有效的。

进阶：

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

题目分析

既然没有给链表的长度, 一个指针是没法用一边扫描实现的. 所以用两个指针, 一开始两个指针slow和fast都指向头结点, 让fast指针先走n步, 之后两个指针一起走, 在fast到NULL时候,

源码

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
#include<bits/stdc++.h>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// @lc code=start
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == NULL) return NULL;
        if(head->next == NULL) return n == 1 ? NULL : head;
        ListNode* slow = head;
        ListNode* fast = slow;
        for(int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        if(fast == NULL) return head->next;
        while(fast->next != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};
// @lc code=end
0%