Leetcode – Remove Nth Node From End of List (Java)
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.
Analysis:
The key to solve this problem is to use two pointers: pre
and cur
. The pre
pointer moves N
steps in the first place, then the cur
pointer and the pre
pointer moves simultaneously until pre
moves to the end of the list. At this point, cur
points at the Nth
node from the end of the list.
To have a clean implementation, we define a dummy
pointer points to the head of the linked list. We let cur
start from the dummy
pointer, once pre
points to the end of the list, the next node of cur
is the target that need to be removed. Then we just call cur.next = cur.next.next
to remove it.
By using the dummy
head, we can also handle the case that the target node is the head of the linked list.
Java Implementation
Here is the Java Implementation to solve the problem of Remove Nth Node From End of linked List.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } class RemoveNthFromHead { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode pre = head; int i = 0; while( i < n && pre != null ) { pre = pre.next; i++; } ListNode dump = new ListNode(-1); dump.next = head; ListNode cur = dump; while(pre != null) { cur = cur.next; pre = pre.next; } cur.next = cur.next.next; return dump.next; } } |