19. 删除链表的倒数第 N 个结点
自己纯手写第一题,递归有点冗杂,开辟了虚拟头节点,而且要特别注意边界条件(当倒数第n个正好是头节点时)。
** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int recursion(ListNode* node,ListNode* &head, int n){ if(node->next == nullptr){ int cnt = 0; return cnt; } int cnt = recursion(node->next, head, n); cnt ++; if(cnt == n){ if(node->next == head){ head = head->next; } else{ node->next = node->next->next; } } return cnt; } ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *node = new ListNode(-1); node->next = head; recursion(node, head, n); return head; } };
大佬的代码永远是那么简洁利落
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int cur = 0; ListNode* removeNthFromEnd(ListNode* head, int n) { if(head == nullptr) return nullptr; head->next = removeNthFromEnd(head->next, n); cur ++; if(cur == n) return head->next; return head; } };
大佬的时间0ms,我的递归4ms,但是我没看出来是由于哪个原因导致时间花费是数倍,感谢如果有好心大佬在评论区能指导一下。
最经典的解法莫过于双指针了。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { int i = 0; ListNode* first = head; ListNode* slow = head; while(i ++ < n){ first = first->next;//快指针先走n步 } if(first == nullptr){ return head->next; } while(first->next != nullptr){ first = first->next; slow = slow->next; } slow->next = slow->next->next; return head; } };