LeetCode #19 Remove Nth Node From End of List
Problem
Given a linked list, remove the n-th node from the end of list and return its head.
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.
Follow up:
Could you do this in one pass?
Solution
Use two pointers runner and walker. Let runner move n steps first and make walker join to move. Once runner reaches the end, walker will be the previous node of the node we want to remove.
Complexity
Obviously it only passes list once so it takes O(n) time if n denotes to amount of nodes in this list. And it only uses O(1) extra space.
