package com.zerroi.leetcode.Three25;

public class RemoveNthFromEnd {
    public static void main(String[] args) {
//        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode head = ListNode.constructLinkedList(new int[]{1,2,3,4,5});
        SolutionFirst solutionFirst = new SolutionFirst();
        solutionFirst.removeNthFromEnd2(head, 2);
    }
}

class SolutionFirst {

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return dummy.next;
    }


    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
        ListNode cur = head;
        int length = length(head);
        if(length == 1) return null;
        if (length == n) return head.next;

        ListNode dummy = new ListNode(0, head);
        for (int i = 1; i <= length - n; i++) {
            cur = cur.next;
            dummy = dummy.next;
        }
        dummy.next = cur.next;

        return head;
    }

    private int length(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}