Given a linked list, remove the nth node from the end of list and return its head.
- Given n will always be valid.
- Try to do this in one pass.
Example:
- Given linked list:
1->2->3->4->5, andn = 2. - After removing the second node from the end, the linked list becomes
1->2->3->5.
C Solution:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummy, *l = &dummy, *r = head;
l->next = head;
while (n--) r = r->next;
while (r) {
l = l->next;
r = r->next;
}
r = l->next;
l->next = l->next->next;
free(r);
return dummy.next;
}
Python Solution:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
tail = head = dummy
while n:
tail = tail.next
n -= 1
while tail.next:
head = head.next
tail = tail.next
head.next = head.next.next
return dummy.next
Summary:
- Dummy is necessary, in case that the head is the one need to delete. This is a corner case, with using dummy head, code is much more concise.
- 3ms, 5.11%
LeetCode: 19. Remove Nth Node From End of List
近期评论