Problem
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?
Solution 0: Cheating! store the nodes in an array
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { if (!head) return nullptr; vector<ListNode *> nodes; ListNode *cur = head; while (cur) { nodes.push_back(cur); cur = cur->next; } if (n == nodes.size()) return head->next; ListNode* nodes_to_remove = nodes[nodes.size()-n]; ListNode* parent = nodes[nodes.size() - n - 1]; parent->next = nodes_to_remove->next; delete nodes_to_remove; return head; } }; |
Solution 1: Two passes
Time complexity: O(L)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { int l = 0; ListNode* cur = head; while (cur) { ++l; cur = cur->next; } if (n == l) { ListNode* ans = head->next; delete head; return ans; } l -= n; cur = head; while (--l) cur = cur->next; ListNode* node = cur->next; cur->next = node->next; delete node; return head; } }; |
Solution 2: Fast/Slow Pointers + Dummy Head / Prev
Fast pointer moves n steps first, and then slow pointer starts moving.
When fast pointer reaches tail, slow pointer is n-th node from the end.
Time complexity: O(L)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* fast = head; for (int i = 0; i < n; ++i) fast = fast->next; ListNode dummy(0); dummy.next = head; ListNode* prev = &dummy; while (fast) { fast = fast->next; prev = prev->next; } ListNode* node = prev->next; prev->next = node->next; delete node; return dummy.next; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = head; while (n-- > 0) fast = fast.next; ListNode prev = dummy; while (fast != null) { fast = fast.next; prev = prev.next; } prev.next = prev.next.next; return dummy.next; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# Author: Huahua class Solution: def removeNthFromEnd(self, head, n): dummy = ListNode(0) dummy.next = head fast, prev = head, dummy for _ in range(n): fast = fast.next while fast: fast, prev = fast.next, prev.next prev.next = prev.next.next return dummy.next |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment