Remove Nth Node From End of List

LeetCode笔记 阅读(378)

编号 : 19      
难度 : <font color="orange">Medium</font>

# 题目 :  
>Given a linked list, remove the n-th node from the end of list and return its head.
>
>**Example**:
>
>>Given linked list: **1->2->3->4->5**, and ***n = 2***.
>>
>>After removing the second node from the end, the linked list becomes **1->2->3->5**.
>
>**Note**:
>
>Given n will always be valid.
>
>**Follow up**:
>
>Could you do this in one pass?
>

# 解 :  
```Cpp
/**
 * 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) {
        /* 令p1 = head,即第1个节点 */
        auto p1 = head;
        
        /* 令p2 = list[n],即第n+1个node */
        auto p2 = head;
        for(int i = 0; i < n && p2 != nullptr; i++)
        {
            p2 = p2->next;
        }
        
        /* 第n+1个节点为nullptr,不存在
         * 说明一共只有n个节点
         * 要删除的是第一个节点
         * 即要删除head 
         */
        if(p2 == nullptr)
        {
            auto temp = head;
            head = head->next;
            delete temp;
        }
        else
        {
            /* p1和p2一起向后移动,保证距离不变,直到p2指向最后一个节点 */
            for(; p2->next != nullptr;)
            {
                p2 = p2->next;
                p1 = p1->next;
            }

            /* 删除p1后面的node*/
            auto temp = p1->next;
            p1->next = p1->next->next;
            delete temp;
        }
        
        /* 返回 */
        return head;
    }
};
```

# 分析 :  
这道题给出一个链表和一个整数n,要求删除链表的**倒数第n**个节点后返回。解法很简单,令`p1`和`p2`之间的距离为n(这里可能有歧义,采用`node[0]`和`node[1]`之间的距离是1的说法),这样一来当`p2`指向链表最后一个节点的时候,`p1`指向倒数第(n+1)个节点,即**`p1`是要删除的节点的钱一个节点**,删除`p1`后面的节点即可。

> 由于题目给的是单向链表,只有`next`指针,要删除一个节点,必须通过它的前一个节点来进行。

这里有一种特殊情况,如果要删除的节点恰好是第一个节点,没有办法让`p1`指向第一个节点的前一个节点。在上述代码中,这种情况会让`p2`初始化的时候为`nullptr`,判断这个条件然后删除第一个节点即可。

> 题目中已经说明输入的n一定是合法的,所以不需要判断。

Markdown使用 帮助


匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

在山的那边,海的那边,有一群蓝精灵。

匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

今天的风儿甚为喧嚣呢。

匿名

在山的那边,海的那边,有一群蓝精灵。

匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!