链表--删除倒数第k个结点（leetcode19

官方题解

使用一个哑结点，这样可以减少很多判断情况

• 方法1：遍历两次

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode first = head;
    while (first != null) {
        length++;
        first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
        length--;
        first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}

• 方法2：使用双指针遍历一次：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

---

我的笨拙的解法，没有用哑结点，导致多了很多判断

    //遍历两次

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = head;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        if (length==1){
            return null;
        }

        int cursor = length-n;

        if (cursor==0){
            ListNode result = head.next;
            return result;
        }else {
            temp = head;
            for (int i = 0; i < cursor-1; ++i) {
                temp = temp.next;
            }
            temp.next = temp.next.next;

            return head;
        }



    }

    //双指针遍历一次

    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode temp1 = head;
        ListNode temp2 = head;
        for (int i = 0; i < n; ++i) {

            temp2 = temp2.next;
        }

        if(temp2==null&&temp1.next == null){
            return null;
        }
        if(temp2==null&&temp1.next != null){
            return head.next;
        }

        while (temp2.next!=null){
            temp1 = temp1.next;
            temp2 = temp2.next;
        }

        temp1.next = temp1.next.next;
        return head;

    }

双指针这个思路要记住