题目:
给定一个链表, 删除链表的倒数第 n 个节点, 并且返回链表的头结点.
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后, 链表变为 1->2->3->5.
思路:
浅显的思路就是遍历一遍取长度, 然后再遍历一遍找到位置删除, 然而这里要遍历两次, 虽然时间复杂度为 O(n). 进阶的想法是使用双指针, 对的, 又是双指针, 只要保证两个指针的间隔为 n, 之后让前一个指针一直到末尾, 两个指针同时递增, 就可以保证后一个指针是倒数第 n 的位置, 需要注意的是几种临界的判断, 自己试着想一下吧.
- /**
- * 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) {
- auto p=head,q=head;
- int distance=0;
- while(n)
- {
- p=p->next;
- n--;
- }
- ListNode* prev=nullptr;
- while(p)
- {
- if(p->next==nullptr)
- {
- prev=q;
- }
- p=p->next;
- q=q->next;
- }
- if(q==head)
- {
- auto r=q->next;
- q->next=nullptr;
- delete q;
- return r;
- }
- prev->next=q->next;
- delete q;
- return head;
- }
- };
来源: http://www.bubuko.com/infodetail-2935745.html