题目介绍
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
1 | Given linked list: 1->2->3->4->5, and n = 2. |
2 | |
3 | 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?
去除单向链表中的倒数第n个节点。n总是有效的，需要只遍历一遍
解
1 | /** |
2 | * Definition for singly-linked list. |
3 | * struct ListNode { |
4 | * int val; |
5 | * ListNode *next; |
6 | * ListNode(int x) : val(x), next(NULL) {} |
7 | * }; |
8 | */ |
9 | class Solution { |
10 | public: |
11 | ListNode* removeNthFromEnd(ListNode* head, int n) { |
12 | if (head == NULL) { |
13 | return head; |
14 | } |
15 | ListNode first(-1); |
16 | first.next = head; |
17 | ListNode* pre = &first; |
18 | while (n-- > 1) { |
19 | head = head->next; |
20 | } |
21 | while (head->next != NULL) { |
22 | head = head->next; |
23 | pre = pre->next; |
24 | } |
25 | pre->next = pre->next->next; |
26 | return first.next; |
27 | } |
28 | }; |
Runtime: 4 ms
Memory Usage: 8.6 MB
