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:
If n is greater than the size of the list, remove the first node of the list.
Try doing it using constant additional space.
Method:
Find the size of the list first, then everything becomes obvious. Note when n == size, then we need to return the second node. Else return the original head.
Solution:
Time: O(n) Space: O(1)
/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */ public class Solution { public ListNode removeNthFromEnd(ListNode A, int B) { if (A == null) return A; int size = 0; ListNode curr = A; while (curr != null) { size ++; curr = curr.next; } if (B >= size) return A.next; curr = A; int num = size - B; int n = 1; while (n < num) { n ++; curr = curr.next; } ListNode next = curr.next; if (next != null) { curr.next = next.next; } else { curr.next = null; }