链表

删除链表元素

Leetcode19.删除链表的倒数第N个节点

问题在于如何定位倒数第n个节点。可以先P1从头遍历n个节点，然后再以P2从头开始遍历，直到P1到尾节点。此时P2刚好会落在倒数第n个节点。

代码如下：

/**
 * Definition for singly-linked list.
 * 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 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null || n == 0) {
            return head;
        }
        // 定义结果
        ListNode result = new ListNode(0, head);
        // pre从head开始遍历
        ListNode pre = head;
        // 从1开始计数，while循环结束后pre刚好指向第n个节点
        int i = 1;
        while(i < n) {
            pre = pre.next;
            i++;
        }
        // cur从result开始遍历。因为要删除倒数第n个节点，所以此处提前一个节点遍历
        ListNode cur = result;
        while(pre.next != null) {
            cur = cur.next;
            pre = pre.next;
        }
        // 删除第n个节点
        cur.next = cur.next.next;
        return result.next;
    }
}