[LeetCode Hot 100] LeetCode19. 删除链表的倒数第N个结点

题目描述

思路一：采用两次遍历

• 第一遍遍历先获取链表的长度length
• 第二次从dummy节点开始走length - n步
• 然后将该节点指向下下个节点

思路二：采用一次遍历

• 设置虚拟节点dummyHead指向head
• 设定双指针p和q，初始都指向虚拟节点dummyHead
• 移动q，直到p与q之间相隔的元素个数为n(即q走n+1步)
• 同时移动p与q，直到q指向的为NULL
• 将p的下一个节点指向下下个节点

方法一：对应思路一

/**
 * 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) {
        ListNode p = head;
        ListNode dummy = new ListNode(0, head);
        ListNode q = dummy;
        int length = 0;
		// p就是用来统计链表的长度
        while (p != null) {
            length ++;
            p = p.next;
        }
		// q是用来找到待删除节点的前一个节点
		// 然后将该节点的next指针指向下下个元素
        for (int i = 0; i < length - n; i ++) {
            q = q.next;
        }
        q.next = q.next.next;
        return dummy.next;
    }
}

方法二：对应思路二

/**
 * 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) {
        // 设置虚拟节点dummyHead指向head
        ListNode dummy = new ListNode(0, head);
        // 设定双指针p和q，初始都指向虚拟节点dummyHead
        ListNode p = dummy, q = dummy;
        // 移动q，直到p与q之间相隔的元素个数为n
        for (int i = 0; i < n + 1; i ++) {
            q = q.next;
        }
        // 同时移动p与q，直到q指向的为NULL
        while (q != null) {
            p = p.next;
            q = q.next;
        }
        // 将p的下一个节点指向下下个节点
        p.next = p.next.next;
        return dummy.next;
    }
}