Leecode19. 删除链表的倒数第 N 个结点——Leecode大厂热题100道系列

╰半夏微凉° 2022-09-14 12:27 129阅读 0赞

## 我是小张同学，立志用最简洁的代码做最高效的表达 ##

--------------------

以下是我个人做的题解，每个题都尽量囊括了所有解法，并做到了最优解，欢迎大家收藏！留言！

#### 传送门——>[**Leecode大厂热题100道系列题解**][Leecode_100] ####

--------------------

### 题目描述 ###

> 题目链接：[https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/][https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]

> 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。  
> 进阶：你能尝试使用一趟扫描实现吗？

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5p2l6ICB6ZOB5bmy5LqG6L-Z56KX5Luj56CB_size_18_color_FFFFFF_t_70_g_se_x_16]

> 示例 1：  
> 输入：head = \[1,2,3,4,5\], n = 2  
> 输出：\[1,2,3,5\]  
>   
> 示例 2：  
> 输入：head = \[1\], n = 1  
> 输出：\[\]  
>   
> 示例 3：  
> 输入：head = \[1,2\], n = 1  
> 输出：\[1\]

> 提示：  
> 链表中结点的数目为 sz  
> 1 <= sz <= 30  
> 0 <= Node.val <= 100  
> 1 <= n <= sz

--------------------

### 题解 ###

先遍历一遍链表，求出长度，再将倒序换为正序，删除节点即可。

解链表题时要着重处理指针，防止指空。 可以采用图示法来解题

class Solution {
        
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
        
            // 链表长度
            int len = 0;
            ListNode* temp = head;
            while(temp) {
        
                len++;
                temp = temp->next;
            }
            // 从后往前计数 ——> 从前往后计数
            n = len - n + 1;
            if(n == 1) return head->next;       // 节点为1 或 删除的是头结点的情况
    
            ListNode* pre = new ListNode();
            pre->next = head;
            while(--n) {
        
                pre = pre->next;
            }
            pre->next = pre->next->next;
            return head;
        }
    };

[Leecode_100]: https://zhanglong.blog.csdn.net/article/details/120545161
[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_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5p2l6ICB6ZOB5bmy5LqG6L-Z56KX5Luj56CB_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ea273f2595e64daea025e88efa7b4e88.png