牛客NC53-删除链表的倒数第n个节点

题目描述

给定一个链表，删除链表的倒数第n个节点并返回链表的头指针 例如，

给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

备注：

题目保证n一定是有效的 请给出请给出时间复杂度为O(n)的算法

思路

1.哈希存储，key为序号，value为指向该位置的指针

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ #include <unordered_map> class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here unordered_map<int,ListNode*> listmap; if(head == nullptr) return nullptr; ListNode* pNow = head; ListNode* pPre = nullptr; int i = 1; while(pNow != nullptr){ listmap[i++] = pNow; pNow = pNow->next; } if(i - 1 == n){//删除头 pPre = head; head = head->next; pPre->next = nullptr; delete pPre; return head; } auto it = listmap.find(i - n ); pNow = it->second; it = listmap.find(i - n - 1); pPre = it->second; pPre->next = pNow->next; pNow->next = nullptr; delete pNow; return head; } };

2.双指针，快指针先走n步，然后慢指针从head，快指针从第n个节点一起走，直到快指针指向nullptr，则慢指针走了链表长度l-n个节点，指向的位置是倒数第n+1个节点(倒数第n个节点正着数应该是l-n+1)

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here if(head == nullptr) return nullptr; ListNode* fast = head; ListNode* slow = head; ListNode* pNow = nullptr; while(n--){ fast = fast->next; } if(fast == nullptr){//待删除节点为头结点 pNow = head; head = head->next; pNow->next = nullptr; delete pNow; return head; } while(fast->next != nullptr){ fast = fast->next; slow = slow->next; } pNow = slow->next; slow->next = pNow->next; pNow->next = nullptr; delete pNow; return head; } };