LeetCodeHot100-第19题-删除链表的倒数第N个结点

19. 删除链表的倒数第 N 个结点

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

进阶做法使用一次遍历删除

思路：快慢指针

• 快指针比慢指针先走n个结点
• 然后同时走，快指针到结尾了，慢指针也到倒数第n个结点了
• 然后直接删除慢指针的下一个结点
• 需要注意：假如删除的是头节点，那么要另作判断

代码实现+详细注释：

 public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
//    使用一趟扫描实现
    class Solution {
    /**
     * 使用快慢指针实现
     * 快指针比慢指针先走n个结点，然后同时走，快指针到结尾了，慢指针也到倒数第n个结点了
     * @param head
     * @param n
     * @return
     */
    // 1 2 3 4 5  删除4
    // 1 2 3 5
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode node1 = head; //快指针
            ListNode node2 = head; //慢指针
            //快指针比慢指针先走n个结点
            while (n-- > 0){
                node1 = node1.next;
            }
            //防止删除头指针
            if(node1 == null) return head.next;
            //快慢指针同时走，快指针到结尾
            while (node1.next != null){
                node1 = node1.next;
                node2 = node2.next;
            }
            //删除第n个指针
            node2.next = node2.next.next;

            return head;
        }
    }