leetcode

题目：Remove Nth Node From End of List

Given a linked list, remove the nth 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.

个人思路：

1、设置两个指针，一个快，一个慢，根据给定的n，让快指针先走n步，之后再同时走，直到快指针走到末节点，此时慢指针走到要删除节点的父节点

2、注意一下边界条件即可，链表为空、删除头节点等情况

代码：

 1 #include <stddef.h>
 2 
 3 struct ListNode
 4 {
 5     int val;
 6     ListNode *next;
 7     ListNode(int x) : val(x), next(NULL) {};
 8 };
 9 
10 class Solution
11 {
12 public:
13     ListNode* removeNthFromEnd(ListNode *head, int n)
14     {
15         if (!head)
16         {
17             return NULL;
18         }
19 
20         ListNode *slow = head;
21         ListNode *fast = head;
22 
23         //快指针先走n步
24         for (int i = 0; i < n; ++i)
25         {
26             fast = fast->next;
27         }
28         //快指针为空，表明要删除的节点为头节点
29         if (!fast)
30         {
31             head = head->next;
32             delete slow;
33             slow = NULL;
34 
35             return head;
36         }
37         //快指针走到最后一个节点时，慢指针走到要删除节点的前一个节点
38         while (fast->next)
39         {
40             slow = slow->next;
41             fast = fast->next;
42         }
43         //删除节点
44         ListNode *deleted = slow->next;
45         slow->next = deleted->next;
46         delete deleted;
47         deleted = NULL;
48 
49         return head;
50     }
51 };
52 
53 int main()
54 {
55     return 0;
56 }

View Code

网上的文章大部分都是这个思路