Remove Nth Node From End of List - 删除链表的倒数第 N 个结点

谁践踏了优雅 2022-10-19 14:59 79阅读 0赞

# **Remove Nth Node From End of List - 删除链表的倒数第 N 个结点** #

[https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/][https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]

Given the head of a linked list, remove the  n n nth node from the end of the list and return its head.  
给你一个链表，删除链表的倒数第  n n n 个结点，并且返回链表的头结点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

**Example 1:**

Input: head = [1,2,3,4,5], n = 2
    Output: [1,2,3,5]

**Example 2:**

Input: head = [1], n = 1
    Output: []

**Example 3:**

Input: head = [1,2], n = 1
    Output: [1]

Constraints:

*  The number of nodes in the list is sz.
 *  1 <= sz <= 30
 *  0 <= Node.val <= 100
 *  1 <= n <= sz

Follow up: Could you do this in one pass?  
进阶：你能尝试使用一趟扫描实现吗？

Maintain two pointers and update one with a delay of `n` steps.

## 1. solution 1 - 一趟扫描 ##

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     struct ListNode *next;
    * };
    */
    
    // 1 <= n <= sz
    struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    	if (NULL == head) {
    		return NULL;
    	}
    
    	struct ListNode *del_node_prev = NULL;
    
    	struct ListNode *del_node = head;
    	struct ListNode *ptr_node = head;
    	int num = 0;
    	while (ptr_node != NULL)
    	{
    		if (num >= n)
    		{
    			del_node_prev = del_node;
    			del_node = del_node->next;
    		}
    
    		ptr_node = ptr_node->next;
    		++num;
    	}
    
    	struct ListNode *ret_head = NULL;
    	if (del_node == head)
    	{
    		ret_head = del_node->next;
    		return ret_head;
    	}
    	else
    	{
    		del_node_prev->next = del_node->next;
    		return head;
    	}
    }

![在这里插入图片描述][20210711233232998.png_pic_center]

## 2. solution 2 - 一趟扫描 ##

在对链表进行操作时，常用的技巧是添加一个哑节点 (dummy node)，它的 `next` 指针指向链表的头节点。这样可以避免对头节点进行特殊的判断。

如果要删除节点 `y`，我们需要知道节点 `y` 的前驱节点 `x`，并将 `x` 的指针指向 `y` 的后继节点。但由于头节点不存在前驱节点，因此我们需要在删除头节点时进行特殊判断。如果我们添加了哑节点，那么头节点的前驱节点就是哑节点本身，此时我们就只需要考虑通用的情况即可。需要自行对内存进行管理。

## References ##

[https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/][https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]

[https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221004/44f0f55cd3c64819b84b0c833b028ad2.png
[20210711233232998.png_pic_center]: /images/20221004/28690b083a684a0fadebf3ae8238acac.png