本文共 1019 字,大约阅读时间需要 3 分钟。
题目:
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后,链表变为 1->2->3->5.
使用两根指针,指针间距离为n-1.当一根指针指向链表尾节点时,证明另一根指针所指节点应该被删除。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* pNode = head; ListNode* fast = head; ListNode* slow = head; //使快指针移动n步,使其与慢指针之间保持一定距离 for (int i = 0; i < n; ++i) fast = fast->next; if (fast == nullptr) { pNode = head->next; delete head; head = nullptr; return pNode; } //使快慢指针同步运动,直到快指针指向链表尾 while (fast->next != nullptr) { fast = fast->next; slow = slow->next; } //使pNext指向该被删除的节点 ListNode* pNext = slow->next; slow->next = pNext->next; //释放空间 delete pNext; pNext = nullptr; return head; }};
转载地址:http://tmdha.baihongyu.com/