Remove Nth Node From End of List

Question

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.

Solution

第一次寫的時候是想到用 HashMap 來記錄每個點到終點的距離，因此當走完一次得知整個 LinkedList 的長度之後，就可以用這個長度減去 n，即可得知欲刪除點的位置。

只不過這個方法會耗費額外的 memory space

Optimal

概念是用快慢指針，並用讓他們都等於 dummy。接著先讓快指針走 n 步，再讓快慢指針一起一步一步走，當快指針走到尾巴時，慢指針剛剛好會落在要刪除點的 prev position

public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n < 0 || head == null) {
            return null;
        }   

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        while (n > 0 && fast != null) {
            fast = fast.next;
            n--;
        }

        while (fast != null && slow != null) {
            fast = fast.next;
            if (fast == null) {
                break;
            }
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }