Leetcode笔记——19.删除链表倒数第n个元素
2019-01-03 本文已影响0人
Scaryang
Problem
Given a linked list, remove the n-th node from the end of list and return its head.
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.
Solution
-
Two Pass
这种方式比较暴力,即先遍历一边链表,然后找到链表的长度,这样我们就可以得到倒数第n个元素的正序数字。缺点就是需要遍历两次。 -
One Pass
一次遍历的话,则需要两个指针,需要一个指针先行n步,然后两个指针同时增加.(突然回忆起大二数据结构的往事,满满的回忆..记得当时的数据结构还考了99分..现在却基本都忘了)
代码如下:
class Solution
{
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode** t1 = &head, *t2 = head;
for(int i = 1; i < n; ++i)
{
t2 = t2->next;
}
while(t2->next != NULL)
{
t1 = &((*t1)->next);
t2 = t2->next;
}
*t1 = (*t1)->next;
return head;
}
};
另一种形式
struct ListNode* front = head;
struct ListNode* behind = head;
while (front != NULL) {
front = front->next;
if (n-- < 0) behind = behind->next;
}
if (n == 0) head = head->next;
else behind->next = behind->next->next;
return head;