给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
思路
- 设置一个哑节点，用来保证可以删除头节点；
- 设置两个节点p,q，让两个节点之间的距离为n, (假设p不动，q往后移动）；
- 当q->next不为空时，p,q两个节点一起往后移动，直到q->next为空，则停止；
- 将p->next的节点进行删除，就是题目的答案。
解答
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
/** * 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 *dummy = new ListNode(-1); if(!head) return head; dummy->next = head; ListNode *prev = dummy; ListNode *cur = dummy; for(int i = 0; i < n; ++i) prev = prev->next; while(prev->next) { prev = prev->next; cur = cur->next; } ListNode *del = cur->next; cur->next = del->next; delete del; del = NULL; ListNode *res = dummy->next; delete dummy; dummy = NULL; return res; } }; |
评论