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

• 一、题目描述
• 二、示例
• 三、难度
• 四、代码
• • Java版

中等

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 class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode p = head, q = head, pre = head;
        //让p先走n步, q指向待删除结点,pre为q的前驱结点
        for (int i = 1; i <= n; ++i) {
            if (p != null)
                p = p.next;
        }
        //q也该出发啦, 让q指向待删除结点,pre为q的前驱结点
        while (p != null) {
            p = p.next;
            pre = q;
            q = q.next;
        }
        //删除q
        if(q == head) head = q.next;
        else pre.next = q.next;
        return head;
    }

    public static void main(String[] args) {
        //lists -> node1 -> node2 -> node3 -> node4
        //1 4 6 5 9
        ListNode node4 = new ListNode(9);
        ListNode node3 = new ListNode(5, node4);
        ListNode node2 = new ListNode(6, node3);
        ListNode node1 = new ListNode(4, node2);
        ListNode lists = new ListNode(1, node1);


        ListNode merge = new Solution().removeNthFromEnd(lists,2);

        while (merge != null) {
            System.out.print(merge.val + " ");
            merge = merge.next;
        }
    }
}