Solution For Remove Duplicates From Sorted List

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

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

Solution:
To remove duplicates from a sorted linked list, we can traverse through the list and compare each node’s value with its previous node’s value. If they are the same, delete the duplicate node.

1. If the given linked list is empty or has only one node, return the head node as it is.
2. Initialize two pointers, current_node and previous_node, to the head node of the linked list. Set previous_node to None initially.
3. Traverse the linked list using current_node, comparing each node’s value with its previous node’s value.
4. If the values are the same, delete the current_node by removing its reference in the linked list.
5. If the values are different, move both current_node and previous_node one step forward.
6. Return the head node of the modified linked list.

Code:

“`python
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return None
current_node = head
previous_node = None
while current_node:
if previous_node and current_node.val == previous_node.val:
previous_node.next = current_node.next
else:
previous_node = current_node
current_node = current_node.next
return head
“`

Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we are only using two pointers to modify the linked list in place.

Step by Step Implementation For Remove Duplicates From Sorted List

/**
 * 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) {
        // if head is null or there is only one node in the list
        if (head == null || head.next == null) {
            return head;
        }
        
        // initialize slow and fast pointers
        ListNode slow = head;
        ListNode fast = head.next;
        
        // loop through the list
        while (fast != null) {
            // if slow.val and fast.val are equal
            if (slow.val == fast.val) {
                // move fast pointer to the next node
                fast = fast.next;
            }
            // if slow.val and fast.val are not equal
            else {
                // move slow pointer to the next node
                slow.next = fast;
                slow = slow.next;
                // move fast pointer to the next node
                fast = fast.next;
            }
        }
        // set slow.next to null to end the list
        slow.next = null;
        
        // return head
        return head;
    }
}

# 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:
        # Base case
        if head == None or head.next == None:
            return head
        
        # Initialize current node and next node
        curr = head
        next = head.next
        
        # Loop through the linked list
        while next != None:
            # If current node's value is equal to next node's value
            if curr.val == next.val:
                # Set next node as current node's next node
                curr.next = next.next
            # If current node's value is not equal to next node's value
            else:
                # Set current node as next node
                curr = next
            # Set next node as current node's next node
            next = curr.next
            
        # Return head node
        return head

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // if head is null or only one node in the list, return head
    if (!head || !head.next) return head;
    
    // create a dummy head node
    let dummy = new ListNode(0);
    dummy.next = head;
    
    // create two pointers, one pointing to the current node, and the other pointing to the previous node
    let prev = dummy;
    let curr = head;
    
    // loop through the list
    while (curr) {
        // if the value at the current node is the same as the value at the next node,
        // move the current node to the next node
        if (curr.next && curr.val === curr.next.val) {
            curr = curr.next;
        } else {
            // if the value at the current node is not the same as the value at the next node,
            // connect the previous node to the current node, and move the previous node and the current node to the next node
            prev.next = curr;
            prev = prev.next;
            curr = curr.next;
        }
    }
    
    // after the loop, connect the previous node to the null node
    prev.next = null;
    
    // return the dummy head's next node
    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) {
        if(head==NULL)
            return head;
        ListNode* temp=head;
        while(temp->next!=NULL)
        {
            if(temp->val==temp->next->val)
            {
                temp->next=temp->next->next;
            }
            else
            {
                temp=temp->next;
            }
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
        {
            return head;
        }
        
        ListNode current = head;
        while(current.next != null)
        {
            if(current.val == current.next.val)
            {
                current.next = current.next.next;
            }
            else
            {
                current = current.next;
            }
        }
        
        return head;
    }
}