19. Remove Nth Node From End of List

三刷 06/2022

Version #1 Two Passes - get length

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.

Memory Usage: 43.2 MB, less than 5.08% of Java online submissions for Remove Nth Node From End of List.

/**

 * 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 curr = head;

        int cnt = 0;

        // c

        // 1

        while (curr != null) {

            cnt++;

            curr = curr.next;

        }

        // m is zero based index of the node to be deleted

        int m = cnt - n;

        if (m == 0) {

            return head.next;

        }

        curr = head;

        // c

        // 1 2 3 - m = 1

        while (m-- > 1) {

            curr = curr.next;

        }

        curr.next = curr.next.next;

        return head;

    }

}

Version #2 One Pass

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 65.32% of Java online submissions for Remove Nth Node From End of List.

Memory Usage: 42.8 MB, less than 17.25% of Java online submissions for Remove Nth Node From End of List.

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        // s

        //     f

        // 1 2 3 4 5

        // s

        // f

        // 1

        ListNode slow = head, fast = head;

        while (n-- > 0 && fast != null) {

            fast = fast.next;

        }

        if (fast == null) {

            return head.next;

        }

        while (fast.next != null) {

            slow = slow.next;

            fast = fast.next;

        }

        slow.next = slow.next.next;

        return head;

    }

}

Version #2 One pass
Two pointers
Find a node which is n nodes away from head -> curr
Define prev as the previous node of head
let curr go forward until it reaches tail, and prev also walk in the same pace
When curr reaches null, prev.next is n nodes away from curr -> we should remove prev.next
-> prev.next = prev.next.next

二刷
50.57 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //prev           p        c   
        //dummy -> 1->2->3->4->5->null
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        while (n > 0) {
            curr = curr.next;
            n--;
        }
        while (curr != null) {
            prev = prev.next;
            curr = curr.next;
        }
        prev.next = prev.next.next;
        return dummy.next;
    }
}


一刷
67.80 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0) return head;
        // n = 1
        //sf
        // 1-> 2 -> null
        ListNode fast = head;
        ListNode slow = head;
        while (n-- > 0 && fast != null) {
            fast = fast.next;
        }
        if (fast == null) return head.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}



Version #1 Two pass
二刷
 99.83 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int len = 0;
        ListNode curr = head;
        while (curr != null) {
            len++;
            curr = curr.next;
        }
        // len = 5, target = 0
        int target = len - n;
        //       p
        // 1->2->3->4->5
        ListNode prev = dummy;
        while (target > 0) {
            prev = prev.next;
            target--;
        }
        prev.next = prev.next == null ? null : prev.next.next;
        return dummy.next;
    }
}


一刷
getLength
14.97 %
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n == 0) return head;
        int len = getLength(head);
        // e.g. len = 5, n = 2 delete index (5 - 2) = 3
        // i 0  1  2  3
        //   1->2->null
        ListNode curr = head;
        if (n == len) return head.next;
     
        for (int i = 0; i < len - n - 1; i++) {
            curr = curr.next;
        }
     
        curr.next = curr.next.next;
        return head;
    }
    private int getLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}