http://n00tc0d3r.blogspot.com/2013/05/remove-n-th-to-end-element-from-list.html
Given a linked list, remove the n-th 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.
Given a linked list, remove the n-th 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.
To do these in one pass, we need two pointers and keep them n+1 nodes away, i.e. having n nodes between the two pointers. We also need to consider special case where n is not valid (i.e. n > list length) or n-th-to-end is the head node.
http://codercareer.blogspot.com/2011/10/no-10-k-th-node-from-end.html
http://blog.csdn.net/kenden23/article/details/16980197
Read full article from LeetCode - Remove Nth Node From End of List | Darren's Blog
public ListNode removeNthFromEnd(ListNode head, int n) {
// pilot is supposed to be n+1 ahead of pre
// so when pilot reaches the end, pre points to the node right before n-th
// that said, there has to be n nodes between the two pointers
ListNode pilot = head, pre = head;
while (pilot != null) {
if (n >= 0) { // forward pilot pointer
--n;
} else { // forward pre pointer
pre = pre.next;
}
pilot = pilot.next;
}
if (n > 0) { // nothing to remove
} else if (n == 0) { // remove head
head = head.next;
} else { // remove n-th
pre.next = pre.next.next;
}
return head;
}
public ListNode removeNthFromEnd(ListNode head, int n) { // ListNode defined in AddTwoNumbers
ListNode end = head, targetAhead = null;
int i = 0;
// Let targetAhead point to the node ahead the one to be removed.
// If such node does not exist, always remove the first node
while (end.next != null) {
end = end.next;
i++;
if (i == n)
targetAhead = head;
else if (i > n)
// Maintain the distance of n between end and targetAhead
targetAhead = targetAhead.next;
}
// Consider the cases of removing the first node and any of the remaining nodes
if (targetAhead == null)
return head.next;
else {
targetAhead.next = targetAhead.next.next;
return head;
}
}
No. 10 - K-th Node from Endhttp://codercareer.blogspot.com/2011/10/no-10-k-th-node-from-end.html
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
if(pListHead == NULL || k == 0)
return NULL;
ListNode *pAhead = pListHead;
ListNode *pBehind = NULL;
for(unsigned int i = 0; i < k - 1; ++ i)
{
if(pAhead->m_pNext != NULL)
pAhead = pAhead->m_pNext;
else
{
return NULL;
}
}
pBehind = pListHead;
while(pAhead->m_pNext != NULL)
{
pAhead = pAhead->m_pNext;
pBehind = pBehind->m_pNext;
}
return pBehind;
}http://blog.csdn.net/kenden23/article/details/16980197
ListNode *removeNthFromEnd(ListNode *head, int n)
{
ListNode dummy(-1);
dummy.next = head;
ListNode *pre = &dummy;
while (--n > 0) head = head->next;
while (head->next)
{
pre = pre->next;
head = head->next;
}
pre->next = pre->next->next;
return dummy.next;
}
ListNode *removeNthFromEnd(ListNode *head, int n)
{
ListNode *end = head;
int i = 0;
for (; i < n; i++)
{
if (end) end = end->next;
else break;
}
if (i != n) return head;
findDeletePos(head, head, head, end);
return head;
}
void findDeletePos(ListNode *(&head), ListNode *pre, ListNode *cur, ListNode *end)
{
while (end)
{
end = end->next;
pre = cur;
cur = cur->next;
}
//注意：删除头指针的时候要做特殊处理
if (pre == cur)
{
head = head->next;
return;
}
pre->next = cur->next;
}
Read full article from LeetCode - Remove Nth Node From End of List | Darren's Blog
