一. 题目描述
Given a linked list, remove the n th node from the end of list and return its head. For 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. Try to do this in one pass.
二. 题目分析
给出一个链表, n是指删除倒数第n个节点。这里的提示n的值默认是合法的。不过其实对输入的n进行异常判断也只需要几句语句。
使用两个指针,即快/慢指针的概念,其中一个指针先走n步,然后慢指针走,等到快指针走到结尾时,,那么慢指针走到了需要删除的节点的前一个位置。
这道题主要难点是考虑边界问题,以及特殊情况(要删除的是头节点),如输入1->2->3->4, n=4,那么需要删除1,此时只需将头指针head = head->next就可以了。
三. 示例代码
#include <iostream>struct ListNode{int value;ListNode* next;ListNode(int x): value(x), next(NULL){};};class Solution{public:ListNode *removeNthFromEnd(ListNode *head, int n){if (head == NULL)return NULL;ListNode *fast = head;ListNode *slow = head;ListNode *temp = head;for (int i = 0; i < n ; i++){fast = fast->next;if (fast)continue;else break;}while (fast){fast = fast->next;temp = slow;slow = slow->next;}if (slow == head){head = head->next;return head;}temp->next = slow->next;delete slow;return head;}};
结果:
四. 小结
实际编程中经常会遇到边界问题,不小心的错误很容易造成程序奔溃,关于指针和链表的使用技巧还需要进一步的学习。
这几年大多是昆明空运来的,