19. Remove Nth Node From End of List

2019/10/21 Leetcode

19. Remove Nth Node From End of List

Tags: ‘Linked List’, ‘Two Pointers’

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution 1

This is not one pass. Find length first, and increment until pointer before node-to-delete. 注意corner case.

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) return null;
    
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode curr = dummy;

    int length = findLength(head);
    int i = length - n;
    
    while (i > 0) {
        i--;
        curr = curr.next;
    }
    
    // curr should be in front of the node to delete
    curr.next = curr.next.next;
    return dummy.next;
}

private int findLength(ListNode node) {
    if (node == null) return 0;
    int i = 0;
    while (node != null) {
        i++;
        node = node.next;
    }
    return i;
}

Solution 2

This looks like ONE PASS, but actually NOT. Should be the same as Solution 1. Two pointers, increment fast n + 1 steps, then procede until fast hit null

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) return null;

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

Search

    Table of Contents