Removing Duplicates from Linked List

To remove duplicates from a linked list, we need to be able to track duplicates. Dictionary/hash table will work well here. We will iterate through the linked list, adding each element to a dictionary/hash table. When we discover a duplicate element, we remove the element and continue iterating. We can do this all in one pass. This solution takes 0(N) time, where N is the number of elements in the linked list.

        public static void RemoveDuplicateNodes(Node node)
        {
            Dictionary<string, string> nodeDictionary = new Dictionary<string, string>();
            Node previousNode = null;
            while (node != null)
            {
                if (nodeDictionary.ContainsKey(node.Data))
                {
                    previousNode.NextNode = node.NextNode;
                }
                else
                {
                    nodeDictionary.Add(node.Data, node.Data);
                    previousNode = node;
                }
                node = node.NextNode;
            }
        }

If we do not have an option to use dictionary, we can iterate with two pointers: current which iterates through the linked list, and runner which checks all subsequent nodes for duplicates. It runs in 0(1) space, but 0(N2 – N Square) time.

        /// <summary>
        /// Removes the duplicate nodes without dictionary.
        /// </summary>
        /// <param name="node">The node.</param>
        public static void RemoveDuplicateNodesWithoutDictionary(Node node)
        {
            while (node != null)
            {
                Node runnerNode = node;
                while (runnerNode.NextNode != null)
                {
                    if (runnerNode.NextNode.Data == node.Data)
                    {
                        runnerNode.NextNode = runnerNode.NextNode.NextNode;
                    }
                    else
                    {
                        runnerNode = runnerNode.NextNode;
                    }
                }
                node = node.NextNode;
            }
        }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s