Leet Code 19.删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。

两次循环

思路：第一次循环找出链表的总长度，第二次循环将倒数第n个节点删除。

在链表头结点前加一个空节点，可以简化操作，对于删除头结点的情况不用特殊处理。

public ListNode removeNthFromEnd(ListNode head, int n) {
        int len=0;
        ListNode index = head;
        while(index != null) {
            len++;
            index = index.next;
        }
        ListNode first = new ListNode (0);
        first.next = head;
        index = first;
        for(int i = 0; i < len - n; index=index.next) {
        }
        index.next = index.next.next;
        return first.next;
    }

一次循环

思路：一次循环就要在循环中确定倒数n个节点的位置。设置两个指针p,q，两个指针直接距离为n，p在前,q在后。当q遍历到最后一个节点时，将p节点删除。

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = new ListNode ( 0 );
        first.next = head;
        ListNode p = first, q = first;
        for(int i = 0; i < n; i++) {
            q = q.next;
        }
        while(q.next != null) {
            p = p.next;
            q = q.next;
        }
        p.next = p.next.next;
        return first.next;
    }