Remove Nth Node From End of List
LeetCode笔记 阅读(516)
编号 : 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一定是合法的,所以不需要判断。