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

leetcode题目链接

题目描述:

解法：1.双指针 2. 遍历节点个数

双指针:

fast 指针先走 n 个结点，然后slow和fast 一直走，直到fast.next为空（到达最后一个结点)，此时 fast - slow == n, 所以slow 指向倒数第 N + 1个结点。

删除slow 后面的结点(倒数第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) {

        ListNode dumpnode = new ListNode(0, head);
        ListNode fast = dumpnode.next, slow = dumpnode;
        for(int i = 1; i < n; i++){
            fast = fast.next;
        }
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dumpnode.next;
    }
}

遍历结点个数

知道了结点个数，很容易找到倒数第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) {

        
        //求结点总数
        int count = 0;
        ListNode temp = head;
        while(temp != null){
            temp = temp.next;
            count++;
        }
        //倒数第N + 1个结点
        int target = count - n;
        //哑舍结点 
        ListNode dumpnode = new ListNode(0, head);
        //寻找倒数第N + 1结点
        temp = dumpnode;
        while(target-- > 0){
            temp = temp.next;
        }
        //删除 *** 作
        temp.next = temp.next.next;
        return dumpnode.next;
    }
}