Deletion of Linked List Node

Remove duplicates from sorted list I

simple, need to ensure that each element appear only once. just use dummy and two pointers to solve the problem..

Remove duplicates from sorted list II

The raw approach is the following: nested loop: time O(n) and space O(1)

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = head, prev = dummy;

        while (cur != null && cur.next != null) {
            if (cur.val != cur.next.val) {
                prev = prev.next;
                cur = cur.next;
            } else {
                while (cur != null && cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                prev.next = cur.next;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

The idea is simple, we maintain two pointers, pre, cur in the given List. Pre pointer is always referring to one position before the cur pointer. When we found pre.val != cur.val && cur.val != cur.next.val, the node referred by cur pointer is a unique node.

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }

    ListNode dummy = new ListNode(0 == head.val ? 1 : 0);// to guarantee the dummy node is not same as the original head.
    dummy.next = head;

    ListNode pre = dummy;
    ListNode cur = head;

    ListNode first = dummy; // the first node in the new unduplicated(result) list.

    while (cur != null && cur.next != null) {
        // in this case, how to define it as a unique list node
        if (cur.val != pre.val && cur.val != cur.next.val) { 
        // we found a unique node, we connect it at the tail of the unduplicated list, 
        // and update the first node.
            first.next = cur;
            first = first.next;
        }
        pre = cur;
        cur = cur.next;
    }

    if (pre.val != cur.val) {  // the last node needs to be dealt with independently
        first.next = cur;
        first = first.next;
    }

    first.next = null;  // the subsequent list is duplicate.

    return dummy.next;
}

Remove nth node from end of list

This problem can be solved in one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by n nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the nth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

note, since we could delete the first listnode, so it's better to create a dummy node.

Remove Linked List Element

use dummy and two pointer approaches to solve the problem..

public ListNode removeElements(ListNode head, int val) {
    // dummy 
    // pre, cur 
    // cur.val == val pre.next = cur.next 

    ListNode dummy = new ListNode(-1);
    dummy.next = head;

    ListNode pre = dummy, cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
            cur = cur.next;
        } else {
            pre = cur;
            cur = cur.next;
        }
    }

    return dummy.next;
}