PU Remove Duplicates from Sorted List

Jan 01, 1970

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example:

  • Given 1->1->2, return 1->2.
  • Given 1->1->2->3->3, return 1->2->3.

C Solution 1:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    struct ListNode *p = head;
    while (p) {
        while (p->next && p->next->val == p->val) p->next = p->next->next;
        p = p->next;
    }
    return head;
}

C Solution 2:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (!head) return head;
    struct ListNode *p = head;
    while (p->next) {
        if (p->next->val == p->val) p->next = p->next->next;
        else p = p->next;
    }
    return head;
}

Python Solution 1:

# 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
        """
        left = head
        while left:
            while left.next and left.next.val == left.val: left.next = left.next.next
            left = left.next
        return head

Python Solution 2:

# 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
        """
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

Summary:

  • python solution 2 is much better

LeetCode: 83. Remove Duplicates from Sorted List