|
题目大意：给定一个链表，删除倒数第N个元素。
分析：有两种方法：
1.两遍循环，第一遍用来确定倒数第N个元素是正着数第几个位置，第二遍循环用来找到这个元素并删除；
2.一遍循环，但是要控制两个指针first与second，我们首先设置一个虚拟头结点dummy，然后将first与second指针均指向dummy，接着将first指针向前移动到第N+1个元素，这个时候再同时向队尾移动双指针，当first指针到达队尾后为空的时候，first指针就指向了将要删除的指针的前一个元素。（这种移动指针感觉得多画一下，空想容易想乱了）
注意：虚拟头结点dummy挺好用的，可以在直接for(int i = 1; i <= n; i++)就移动到第n个位置，直接从真实head移动的话得稍微分类一下或者调整一下i的开始下标。
方法一代码：
ListNode* removeNthFromEnd(ListNode* head, int n) {
int len = 0;
ListNode *tmp = head, *last = NULL;
while(tmp != NULL) {
len++;
tmp = tmp -> next;
}
int index = len - n + 1;
if(index == 1) {
if(head -> next == NULL) {
return NULL;
} else {
return head -> next;
}
}
if(index == 2) {
head->next = head->next->next;
return head;
}
ListNode *left, *right;
tmp = head;
for(int i = 2; i <= index; i++) {
tmp = tmp -> next;
if(i == index - 1) {
left = tmp;
}
if(i == index) {
right = tmp -> next;
}
}
left->next = right;
return head;
}
方法二代码：
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummy = new ListNode(0);
dummy -> next = head;
ListNode *first = dummy, *second = dummy;
for(int i = 1; i <= n + 1; i++) {
first = first -> next;
}
while(first != NULL) {
first = first -> next;
second = second -> next;
}
ListNode *tmp = (second -> next) -> next;
second -> next = tmp;
return dummy -> next;
}
| 
转播
