Question

Formatted question description: https://leetcode.ca/all/82.html

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

Algorithm

In this problem, we need to remove all duplicates from a linked list. The linked list may have duplicates at the beginning, and hence, deleting nodes from the beginning can change the head pointer of the linked list. Therefore, we need to define a new node, link the original linked list to it, and then define two pointers: a predecessor pointer and a current pointer. Both pointers start from the new node, and the current pointer moves down the list.

If the current pointer encounters the same value as its predecessor, it moves forward until it finds a different value. Then, the next of the predecessor pointer is updated to point to the different element below.
If the first element traversed by the current pointer is not the same as its predecessor, we move the predecessor pointer down one position.

In the end, we need to return the head pointer of the linked list.

Code

public class Remove_Duplicates_from_Sorted_List_II {

	public ListNode deleteDuplicates(ListNode head) {

		if (head == null) {
			return head;
		}

		ListNode dummy = new ListNode(0);
		dummy.next = head;

		ListNode prev = dummy;
		ListNode current = head;

		while (current != null) {

			boolean dup = false;

			// probe next to see if duplicate
			while (current.next != null && current.val == current.next.val) {
				current = current.next;
				dup = true;
			}

			if (dup) { // prev staying the same
				prev.next = current.next;
				current = current.next;
			} else {
				prev = current;
				current = current.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 deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int val = cur.next.val;
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

// OJ: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy, *tail = &dummy;
        while (head) {
            int val = head->val;
            if (head->next && head->next->val == val) {
                while (head && head->val == val) head = head->next;
            } else {
                tail->next = head;
                tail = head;
                head = head->next;
            }
        }
        tail->next = nullptr;
        return dummy.next;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = ListNode(-1, head)
        cur = dummy
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                val = cur.next.val
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

############

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
  def deleteDuplicates(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    dummy = ListNode(-1)
    dummy.next = head
    p = dummy
    while p.next:
      if p.next.next and p.next.val == p.next.next.val:
        z = p.next
        while z and z.next and z.val == z.next.val:
          z = z.next
        p.next = z.next
      else:
        p = p.next
    return dummy.next

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function deleteDuplicates(head: ListNode | null): ListNode | null {
    const dummy = new ListNode(101, head);
    let pev = dummy;
    let cur = dummy;
    let count = 1;
    while (cur != null) {
        if (cur.val !== (cur.next ?? {}).val) {
            if (count === 1) {
                pev = cur;
            } else {
                pev.next = cur.next;
            }
            count = 0;
        }
        cur = cur.next;
        count++;
    }
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let cur = head;
    let pre = new ListNode(0);
    pre.next = head;
    let dummy = pre;
    let rep = false;
    if (!head || !head.next) {
        return head;
    }
    while (cur) {
        while (cur.next && cur.val == cur.next.val) {
            cur = cur.next;
            rep = true;
        }
        if (rep) {
            pre.next = cur.next;
            cur = cur.next;
        } else {
            pre = cur;
            cur = cur.next;
        }
        rep = false;
    }
    return dummy.next;
};

public class Solution {
    private ListNode newHead;
    private ListNode last;
    private ListNode candidate;
    private int count;

    public ListNode DeleteDuplicates(ListNode head) {
        while (head != null)
        {
            if (candidate == null || candidate.val != head.val)
            {
                TryAppend();
                candidate = head;
                count = 1;
            }
            else
            {
                ++count;
            }

            head = head.next;
        }
        TryAppend();
        if (last != null) last.next = null;
        return newHead;
    }

    private void TryAppend()
    {
        if (count == 1)
        {
            if (newHead == null)
            {
                newHead = last = candidate;
            }
            else
            {
                last.next = candidate;
                last = last.next;
            }
        }
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn delete_duplicates(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode::new(101)));
        let mut pev = dummy.as_mut().unwrap();
        let mut cur = head;
        let mut pre = 101;
        while let Some(mut node) = cur {
            cur = node.next.take();
            if node.val == pre || (cur.is_some() && cur.as_ref().unwrap().val == node.val) {
                pre = node.val;
            } else {
                pre = node.val;
                pev.next = Some(node);
                pev = pev.next.as_mut().unwrap();
            }
        }
        dummy.unwrap().next
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	pre, cur := dummy, head
	for cur != nil {
		for cur.Next != nil && cur.Next.Val == cur.Val {
			cur = cur.Next
		}
		if pre.Next == cur {
			pre = cur
		} else {
			pre.Next = cur.Next
		}
		cur = cur.Next
	}
	return dummy.Next
}

82 - Remove Duplicates from Sorted List II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions