19. Remove Nth Node From End of List

2019-11-08 01:09:13

字体：大中小

来源：转载

供稿：网友

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.

解法一，双指针大法：

class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { if(head == NULL || n <= 0) return head; ListNode* fast = head; for(int i=0; i<n && fast!=NULL; ++i) fast = fast->next; if(fast == NULL) return head->next; ListNode* slow = head; while(fast->next != NULL){ slow = slow->next; fast = fast->next; } slow->next = slow->next->next; return head; }};

解法二，stack+二级指针：

class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { if(head == NULL || n <= 0) return head; ListNode** pp = &head; std::stack<ListNode**> st; while(*pp != NULL){ st.push(pp); pp = &((*pp)->next); } ListNode** target = NULL; int count = 0; while(!st.empty()){ target = st.top(); st.pop(); if(++count == n) break; } *target = (*target)->next; return head; }};

解法二可以通过测试用例，但是解法二没有对N的长度是否大于链表长度进行判断，不过如果N的长度=链表长度，解法二而*target=(*target)->next会满足要求删除了头部。

解法一和二实际上都没有处理链表长度K远远小于N的情况，实际上这种情况直接返回head就可以了。

所以解法一最完整的写法应该是：

class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { if(head == NULL || n <= 0) return head; ListNode* fast = head; int i; for(i=0; i<n && fast!=NULL; ++i) fast = fast->next; if(fast == NULL){ if(i == n) return head->next; else return head; } ListNode* slow = head; while(fast->next != NULL){ slow = slow->next; fast = fast->next; } ListNode* tmp = slow->next; slow->next = slow->next->next; delete tmp; //加上delete return head; }};

解法二就不写了。

上一篇：LeetCode-441. Arranging Coins

下一篇：weightad interval scheduling problems