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; } } |
