package com.zmz.algorithm.listnode;

/**
 * @author 张明泽
 * Create by 2022/5/29 13:38
 * 删除链表的倒数第N个节点
 * LeetCode-19
 */
public class DeleteListNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        ListNode result = delete(head,2);
        traverse(result);
    }

    /**
     * 快慢指针 先让快的走 target 距离 然后在一起走
     * 当快指针指向末尾的时候 慢指针的指向就是目标
     * @return
     */
    public static ListNode delete(ListNode listNode, int target) {
        ListNode header = new ListNode(-1);
        header.next = listNode;
        ListNode quick = header;
        ListNode slow = header;
        while (target-- > 0) {
            quick = quick.next;
        }
        int index = 0;
        while (quick.next != null) {
            index++;
            quick = quick.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return header.next;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public static void traverse(ListNode listNode) {
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}