Category Archives: Linked list

Deleting duplicates from a sorted linked list

Given a sorted linked list, We have to delete all the duplicates in that list. For example, If we get the following list
1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 4 -> 5
The output should be
1 -> 2 -> 3 -> 4 ->5

To solve this problem we take two pointers current and next, we iterate through the list until the next pointer reaches the end of the list.

In each iteration we compare the data at current and next nodes. If they are equal, we delete the next node, and the next pointer is advanced to the subsequent node. Take a look at the pictorial representation of this step to understand better.


Here is the working code of C++ for this.

Sorting a linked list using bubble sort

How do we sort a linked list? 
In this post, we see one such method using bubble sort algorithm.

We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.

We first find the length of the linked list (len). The outer loop iterates for (len-1) times and the inner loop iterates for (len-1-i) times.

Since we cannot access the linked list elements by their indices, we use two pointers to keep track of the current node and the next node which will be compared and swapped in each iteration.

Here is the Object Oriented C++ implementation. 
 

Finding the nth node from the end in a linked list

Given a linked list, how do efficiently find the nth node from the end?

For example  in the following linked list, 3rd node from the end is ‘6’.

2 -> 1 -> 6 -> 5 -> 9

One obvious method is to find the length of the linked list (len) by going through the list. calculate the difference (len – n). Again traverse the list (len – n) times to get the required node. Though this approach is O(n), we traverse the list twice.

We can do it in just one iteration itself. We take two pointers one main pointer (ptr) and one helper pointer (hPtr). First we travel a distance of n nodes with hPtr. Then we start from the beginning with main pointer also. By the time the hPtr reaches the end, ptr would be pointing to the nth node from the end.

Here is Object Oriented implementation of this in C++


Inserting an element into a sorted linked list

Given a sorted linked list, how do we insert data into the list in proper order?
This is nothing but a step in insertion sort. Simply iterate through the elements to find the position for given number and insert at that position.
Here is the Java code to do that. I have used the LinkedList class available in java utilities so that we need not implement the entire linked list class on our own.

import java.util.LinkedList;
import java.util.ListIterator;

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/11/13
* Time: 5:32 AM
* To change this template use File | Settings | File Templates.
*/
public class SortedListDemo {
public static void main(String[] args)
{
LinkedList<Integer> sortedList = new LinkedList<Integer>();

sortedInsert(sortedList, 3);
sortedInsert(sortedList, 1);
sortedInsert(sortedList, 6);
sortedInsert(sortedList, 4);
sortedInsert(sortedList, 2);
sortedInsert(sortedList, 5);

System.out.println("Contents of the sorted list: " + sortedList);
}
public static void sortedInsert(LinkedList<Integer> sList, int data)
{
int pos = 0;

for(int listData : sList )
{
if( listData > data)
break;
pos++;
}

//Alternative code for the above loop using an iterator
/*
ListIterator<Integer> listIterator = sList.listIterator();
while( listIterator.hasNext() && listIterator.next() < data )
pos++;
*/
//insert the data in its correct position
sList.add(pos, data);
}
}

Finding the middle of the linked list

Given a single linked list, how do you find the middle of the list?

One simple method is to traverse through the list twice once to find it’s length, and second to navigate to the middle of the list by traversing length/2 nodes. Even though this method runs in O(n) time, there is still a chance of improving this method. 

In this method we traverse the list only once. We take two pointers, one, a slow pointer which will advance one node at a time; and a fast pointer which will advance two nodes at a time. we iterate through the list until the fast pointer reaches the end of the list. At this stage, the slow pointer would be pointing to the middle of the linked list.

Following is the C++ function which implements this method. For working program please visit this post.


 SLLNode* getMiddle()
{
//if the list is empty or has a single node; return head
if( head == NULL || head->getNext() == NULL )
return head;

SLLNode *slow = head;
SLLNode *fast = head->getNext();

while( fast != NULL )
{
//move fast pointer two steps ahead
if( fast->getNext() != NULL )
{
fast = fast->getNext()->getNext();
}
else
break;
//move slow pointer one step
slow = slow->getNext();
}
return slow;
}

Finding the length of a linked list

In this post we will see an algorithm to find the length of the linked list. Here singly linked list is implemented in Object Oriented Programming (OOP) paradigm in C++. The algorithm is very simple. Just start at the beginning of the linked list, move to next until you reach the end of the list, incrementing a counter in each iteration. Following is the source C++ code for the same.

#include <iostream>

using namespace std;

//Node definition for a single linked list
class SLLNode
{
private:
//data member
int data;
//pointer to next node in the linked list
SLLNode *nextPtr;

public:

//Single argument constructor
//initializes data with d, next pointer to NULL
SLLNode(int d):data(d),nextPtr(NULL)
{
}
//to initialize both members
SLLNode(int d,SLLNode* next):data(d),nextPtr(next)
{
}
//returns the data
int getData()
{
return data;
}
//sets the data
void setData(int d)
{
this->data = d;
}
//gets the next pointer
SLLNode* getNext()
{
return this->nextPtr;
}
//sets the next pointer
void setNext(SLLNode *ptr)
{
this->nextPtr = ptr;
}
};

//defines the actual single linked list
class SinglyLinkedList
{
private:
//maintain two pointers to the start and the end
//so that we can append at the end easily (constant time complexity)
SLLNode * head;
SLLNode * tail;
public:
SinglyLinkedList()
{
head = NULL;
tail = NULL;
}
//adds the node to the end of the list
void appendNode(SLLNode* ptr)
{
//check if list is empty
if( head == NULL)
{
//update both the pointers
head = tail = ptr;
}
else //simply append at the end, and move the tail pointer
{
tail->setNext(ptr);
tail = tail->getNext();
}
}
//gets the length of the list
int getLength()
{
int length = 0;

SLLNode* ptr = head;

while ( ptr != NULL )
{
length++;
ptr = ptr->getNext();
}
return length;
}
};

int main()
{
SinglyLinkedList list;
list.appendNode(new SLLNode(1));
list.appendNode(new SLLNode(2));
list.appendNode(new SLLNode(3));
list.appendNode(new SLLNode(4));
cout<<"Length: "<<list.getLength()<<endl;
return 0;
}