LeetCode - Remove Nth Node From End of List
Problem description
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
1
2
3
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.
Follow up:
Could you do this in one pass?
Analysis
The basic idea is to use two pointer, one is head and another one attempt to reach the end of the list. And the distance between them are (n + 1) step, so that when the second pointer reach the end of the list, the first one is at the right position, which is the node before the node should be deleted.
One thing to remember is that we should use a fake head to avoid the situation in case we should remove the head node.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class RemoveNthNodeFromEndofList {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode l1 = dummy, l2 = dummy;
while (n > 0) {
l2 = l2.next;
n--;
}
while (l2.next != null) {
l1 = l1.next;
l2 = l2.next;
}
l1.next = l1.next.next;
return dummy.next;
}
}
Another solution is to iterate the LinkedList twice, first get the len of the LinkedList, and second run len - n + 1 to get the right position.
What to improve
- dummy node in LinkedList is always useful