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

逃离我推掉我的手 2022-05-11 11:16 171阅读 0赞

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

#### 题目描述 ####

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

#### 示例 ####

给定一个链表: 1->2->3->4->5, 和 n = 2.  
当删除了倒数第二个节点后，链表变为 1->2->3->5.

**说明**：  
给定的 n 保证是有效的。

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

#### 解决方法 ####

考察链表相关操作，首先找到倒数第n+1个节点，然后就是基本的链表删除操作

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) { 
            
            int len=0; //计算链表长度
            ListNode *l1=head;
            while(l1){ 
                len++;
                l1=l1->next;
            }
            if (len<=1) { head=NULL;return head;}//特殊情况1：只有一个节点
            if (len==n) { head=head->next;return head;}//特殊情况2：删除的是第一个节点
            
            int count=0; //找到倒数第n+1个节点
            ListNode *pos=head;
            while(pos && count<len-n-1){ 
                pos=pos->next;
                count++;
            }
            
            ListNode *q=pos->next; //删除倒数第n个节点（q位置）
            pos->next=q->next;
            delete q;
            
            return head;
        }
    };

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