给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
思路1
先遍历一遍链表,得出节点数count,倒数第n个节点,就是正着数第count-n+1,再遍历到该点
int count=1;
struct ListNode *p=head;
while(p->next!=NULL){
p=p->next;
count++;
}
if(count==1){
head=NULL;
return head;
}
int c=count-n;
struct ListNode *temp=head;
while(c>1){
temp=temp->next;
c--;
}
if(c==0){
head=head->next;
return head;
}
temp->next=temp->next->next;
return head;
思路2
利用双指针解法(前指针、后指针),让前指针先走N步,再让两个在指针同时后移,直到前指针到达尾部,此时,后指针的下一个节点就是要被删除的节点了。
struct ListNode* front = head;
struct ListNode* behind = head;
for(int i=0;i<n;++i){
front=front->next;
}
if(front==NULL){
return head->next;
}
while(front->next!=NULL){
front=front->next;
behind=behind->next;
}
behind->next = behind->next->next;
return head;