leetcode 19 Remove Nth Node From End of List
leetcode 19 Remove Nth Node From End of List
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.
解决方案：
Because the linked list have no knowledge about the previous nodes, we have to provide such information.
The difference between the final node and the to-be-delete node is N, hence we can utilize this information. •front pointer points to the node which is N step away from the to-be-delete node •rear pointer points to the to-be-delete node.
The algorithms is described as below: •First driving front pointer N step forward. •Secondly, move the 2 pointers 1 step ahead till the front pointer reach the end simultaneously, which will cause the rear pointer points to the previous node of the to-be-delete node. • Finally, jump the rear->next node by rear->next = rear->next->next.
下面的代码稍微有一个疑问：
http://bbs.csdn.net/topics/391029228
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode new_head(-1);
new_head.next = head;
ListNode *front = &new_head, *rear = &new_head;
for (int i = 0; i < n; i++)
front = front->next;
while (front->next != NULL) {
front = front->next;
rear = rear->next;
}
ListNode *tmp = rear->next;
rear->next = rear->next->next;
delete tmp;
head = new_head.next;
return head;
}
};python解决方案：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode} head
# @param {integer} n
# @return {ListNode}
def removeNthFromEnd(self, head, n):
dummyHead = ListNode(0)
dummyHead.next = head
slow = fast = dummyHead
for i in range(n):
fast = fast.next
while fast and fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummyHead.next