82. Remove Duplicates from Sorted List II

Description

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.

Solutions

Solution 1: Single Pass

Thinking

The first idea is count frequencies, then rebuild a list of values that appear once. Correct, and \(n \le 300\) is tiny, but that wastes “already sorted, so duplicates are adjacent” and uses extra \(O(n)\) space.

The bottleneck is not using adjacency. Equal values form a contiguous run; one pass decides whether the whole run stays.

The head may be deleted, so we need a dummy. And when a run is dropped, the predecessor must not advance into it. Keep \(pre\) on the last kept node and slide \(cur\) over the current value: if \(pre.next\) is still \(cur\), the run has length one and \(pre\) moves; otherwise skip the whole run.

First, we create a dummy head node \(dummy\), and set \(dummy.next = head\). Then we create a pointer \(pre\) pointing to \(dummy\), and a pointer \(cur\) pointing to \(head\), and start traversing the linked list.

When the node value pointed by \(cur\) is the same as the node value pointed by \(cur.next\), we let \(cur\) keep moving forward until the node value pointed by \(cur\) is different from the node value pointed by \(cur.next\). At this point, we check whether \(pre.next\) is equal to \(cur\). If they are equal, it means there are no duplicate nodes between \(pre\) and \(cur\), so we move \(pre\) to the position of \(cur\); otherwise, it means there are duplicate nodes between \(pre\) and \(cur\), so we set \(pre.next\) to \(cur.next\). Then we continue to move \(cur\) forward. Continue the above operation until \(cur\) is null, and the traversal ends.

Finally, return \(dummy.next\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the linked list.

Python3JavaC++GoTypeScriptRustJavaScriptC#

# 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: Optional[ListNode]) -> Optional[ListNode]:
        dummy = pre = ListNode(next=head)
        cur = head
        while cur:
            while cur.next and 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

/**
 * 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(0, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            while (cur.next != null && 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;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* pre = dummy;
        ListNode* cur = head;
        while (cur) {
            while (cur->next && 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;
    }
};

/**
 * 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
}

/**
 * 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(0, head);
    let pre = dummy;
    let cur = head;
    while (cur) {
        while (cur.next && cur.val === cur.next.val) {
            cur = cur.next;
        }
        if (pre.next === cur) {
            pre = cur;
        } else {
            pre.next = cur.next;
        }
        cur = cur.next;
    }
    return dummy.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.
 * 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) {
    const dummy = new ListNode(0, head);
    let pre = dummy;
    let cur = head;
    while (cur) {
        while (cur.next && cur.val === cur.next.val) {
            cur = cur.next;
        }
        if (pre.next === cur) {
            pre = cur;
        } else {
            pre.next = cur.next;
        }
        cur = cur.next;
    }
    return dummy.next;
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            while (cur.next != null && 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

Description

Solutions

Solution 1: Single Pass

Comments