題目
Given a linked list, remove the nth node from the end of list and return its head.
For 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.
Note:
Given n will always be valid.
Try to do this in one pass.
分析
給定一個(gè)鏈表发框，移除從隊(duì)尾向前數(shù)的第n個(gè)節(jié)點(diǎn)恰起。
由于是鏈表，只能從前向后尋找數(shù)據(jù)，所以先遍歷看一共多少數(shù)據(jù)句葵，即可知道要移除的倒數(shù)第幾個(gè)數(shù)字是正數(shù)的第幾個(gè)數(shù)字截汪。
之后尋找該幾點(diǎn)和其前節(jié)點(diǎn)，然后替換next指針即可踪旷，C代碼如下曼氛，已通過。
也可以使用兩個(gè)指針令野，先讓一個(gè)走n步舀患，另一個(gè)接著走。那么當(dāng)?shù)谝粋€(gè)指針達(dá)到鏈表尾部時(shí)候气破，第二個(gè)指針指向第n個(gè)節(jié)點(diǎn)聊浅。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode * p=head, *q=head;
int length=0;
while(p!=NULL)
{
p=p->next;
length++;
}
p=head;
if(n>length)
n=1;
else
n=length-n+1;
while(n-1>0&&p->next!=NULL)
{
q=p;
p=p->next;
n--;
}
if(q==p)
{
head=head->next;
}
else
{
q->next=p->next;
}
return head;
}
