删除单链表中倒数第k个结点

A：要删除单链表中倒数第k个结点，可以使用双指针法。首先定义两个指针，一个指针先走 k 步，然后再让第二个指针和第一个指针一起走，当第一个指针指向链表尾部时，第二个指针指向的就是倒数第 k 个结点的前一个结点。

接下来，只需要将第二个指针指向的结点的 next 指针指向倒数第 k 个结点的下一个结点即可。

具体代码实现如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    for i in range(n):
        first = first.next
    while first.next is not None:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

这里使用了 dummy 结点，它的作用是防止第二个指针指向空结点，在链表只有一个结点并且要删除时特别有用。

相关问题

用单指针删除单链表中倒数第k个结点

题目描述：

给定一个单链表的头指针和倒数第 k 个结点，要求在单链表中删除该倒数第 k 个结点，并返回删除后的单链表的头指针。

例如，给定单链表为 1->2->3->4->5，倒数第 2 个结点为 4，那么删除该结点后的单链表为 1->2->3->5。

解题思路：

双指针法。可以定义两个指针 slow 和 fast，初始时两个指针同时指向头结点。让 fast 先向前走 k 步，然后 slow 和 fast 同时开始向前走，直到 fast 指向尾结点。

此时，slow 指向的结点就是倒数第 k 个结点的前一个结点。然后我们只需要将 slow 指向的结点的下一个结点删除即可。

需要注意，如果删除的是头结点，那么需要将头指针向后移动一个位置。

代码实现：

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

ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *slow = head, *fast = head;

// fast 先向前走 k 步
for (int i = 0; i < n; i++) {
fast = fast->next;
}

// 如果 fast 为空，说明删除头结点
if (!fast) {
ListNode *tmp = head;
head = head->next;
delete tmp;
return head;
}

// slow 和 fast 同时向前走
while (fast->next) {
slow = slow->next;
fast = fast->next;
}

// 删除 slow 指向的结点的下一个结点
ListNode *tmp = slow->next;
slow->next = slow->next->next;
delete tmp;

return head;
}

删除单链表中倒数第k个结点（简化）c语言

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *fast = head, *slow = head;
// fast指针先走n步
for (int i = 0; i < n; i++) {
fast = fast->next;
}
// 如果fast指针已经到了链表尾部，说明要删除的是头结点
if (fast == NULL) {
head = head->next;
free(slow);
return head;
}
// 同时移动fast和slow指针，直到fast到达链表尾部
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
// 删除倒数第n个结点
struct ListNode* tmp = slow->next;
slow->next = slow->next->next;
free(tmp);
return head;
}