Ronzii's Blog

Just your average geek's blog

Given a single linked list, A->B->C->D->E->F, convert this to B->A->D->C->F->E…

struct node
{
    struct node* next;
    char data;
};
typedef struct node Node;
Node* altSwap(Node* current)
{
    Node* head = current;
    Node* temp;
    Node* previous=NULL;
    while(current && current->next)
    {
        temp = current->next;
        if(current==head)
        {
            head =temp;
        }
        current->next = temp->next;
        temp->next = current;
        if(previous!=NULL)
            previous->next = temp;
        previous = current;
        current = current->next;
    }
    return head;
}

March 8, 2012 Posted by | C++ | , , , , | Leave a comment

Convert Sorted Circular Doubly Linked List into a Balanced Search Tree

struct node
{
	int value;
	struct node* previous;
	struct node* next;
};
typdef struct node Node;
Node* getMiddle(Node* front)
{
	if(front==NULL)
	{
		return NULL;
	}
	else
	{
		Node* slow = front;
		Node* fast = front->previous;
		do
		{
			fast = fast->next->next;
			slow = slow->next
		}while(fast->value > slow->value && fast!=end && fast!=start);
		return slow;
	}
}
Node* convertDLLToTree(Node* front)
{
	// In case of empty list
	if(front==NULL)
	{	
		return NULL;
	}
	// Single Node - Base Case
	else if(front==front->next && front==front->previous)
	{	
		return front;
	}
	else
	{
		// Get Middle
		Node* middle = getMiddle(front);
		// partition into 2 DLL centered at middle
		middle->previous->next = front; // front->previous = middle->previous
		front->previous->next = middle->next; //
		// Find middle of sub DLL
		middle->previous = convertDLLToTree(front);
		middle->next = convertDLLToTree(middle->next);
		return middle;
	}
}

February 27, 2012 Posted by | C++ | , , , , | Leave a comment

Convert Tree into Sorted Circular Doubly Linked List

struct node
{
	int value;
	struct node* left;
	struct node* right;
};
typedef struct node Node;
// Previous tracks the parent
// Head tracks the head of the Circular DLL
Node* treeToList(Node* current, Node* &previous=NULL, Node* &head=NULL)
{
	if(current==NULL)
	{
		return 0;
	}
	treeToList(current->left,previous,head);
	current->left = previous;
	if(previous)
	{
		previous->right = current;
	}
	else
	{
		// Left most node is head of list
		head = current;
	}
	// Save right subtree pointer for recursive call
	Node* right = current->right;
	// Make list circular
	head->left = current;
	current->right = head;
	previous = current;
	treeToList(right,previous,head);
}

February 27, 2012 Posted by | C++ | , , , , | Leave a comment

Intersecting node of a Y shaped linked list

#include<cstdio>
#include<cstdlib>
struct node
{
    int data;
    struct node* next;
};

int getCount(struct node* head)
{
    struct node* current = head;
    int count = 0;

    while (current != NULL)
    {
        count++;
        current = current->next;
    }

    return count;
}
int _getIntesectionNode(int d, struct node* head1, struct node* head2)
{
    int i;
    struct node* current1 = head1;
    struct node* current2 = head2;

    for(i = 0; i < d; i++)
    {
        if(current1 == NULL)
        {
            return -1;
        }
        current1 = current1->next;
    }

    while(current1 !=  NULL && current2 != NULL)
    {
        if(current1 == current2)
            return current1->data;
        current1= current1->next;
        current2= current2->next;
    }

    return -1;
}
int getIntesectionNode(struct node* head1, struct node* head2)
{
    int c1 = getCount(head1);
    int c2 = getCount(head2);
    int d;

    if(c1 > c2)
    {
        d = c1 - c2;
        return _getIntesectionNode(d, head1, head2);
    }
    else
    {
        d = c2 - c1;
        return _getIntesectionNode(d, head2, head1);
    }
}
int main()
{
    /*
      Create two linked lists

      1st 3->6->9->15->30
      2nd 10->15->30

      15 is the intersection point
    */
    struct node* newNode;
    struct node* head1 = (struct node*) malloc(sizeof(struct node));
    head1->data  = 10;

    struct node* head2 = (struct node*) malloc(sizeof(struct node));
    head2->data  = 3;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 6;
    head2->next = newNode;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 9;
    head2->next->next = newNode;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 15;
    head1->next = newNode;
    head2->next->next->next  = newNode;

    newNode = (struct node*) malloc (sizeof(struct node));
    newNode->data = 30;
    head1->next->next= newNode;

    head1->next->next->next = NULL;

    printf("\n The node of intersection is %d \n", getIntesectionNode(head1, head2));
    return 0;
}

July 29, 2011 Posted by | C++ | , | Leave a comment

Sorting in Linked Lists

Merge sort is the perfect algorithm for sorting linked list’s.  The frontBackSplit() function is used to return a pointer to the middle element of a linked list. It uses the hare and tortoise algorithm to find the middle element. It returns n/2 th element in the list in case it is even and if it is odd it returns the n/2 +1 th element. The front node contains the head of the 1st list  and rear contains the head of the 2nd.

The SortedMerge() function is used to merge two sorted sub-lists. The complexity of this code is O(n*log(n))

void frontBackSplit(Node* source,Node* &front, Node* &rear)
{
    Node* slow;
    Node* fast;
    if(source==NULL || source->next==NULL)
    {
        front = source;
        rear = NULL;
    }
    else
    {
        slow=source;
        fast=source->next;
        while(fast!=NULL && slow!=NULL)
        {
            fast=fast->next;
            if(fast!=NULL)
            {
                slow=slow->next;
                fast=fast->next;
            }
        }
        front = source;
        rear = slow->next;
        slow->next = NULL;
    }
}
Node* SortedMerge(Node* a, Node* b)
{
    Node* result= NULL;
    if(a==NULL) return b;
    else if(b==NULL) return a;
    else if(a->value < b->value)
    {
        result = a;
        result->next = SortedMerge(a->next,b);
    }
    else
    {
        result = b;
        result->next = SortedMerge(a,b->next);
    }
    return result;
}
void mergeSort(Node* &front)
{
    Node* head = front;
    Node* a;
    Node* b;
    if(head==NULL || head->next == NULL)
    {
        return;
    }
    else
    {
        frontBackSplit(head,a,b);
        mergeSort(a);
        mergeSort(b);
        front = SortedMerge(a,b);
    }
}

July 8, 2011 Posted by | C++ | , , | Leave a comment

Cycle finding Algorithms in Linked List

Floyd’s cycle finding algorithm uses the tortoise and hare algorithm. It consists of two pointers i.e fast and slow. The fast node traverses 2 nodes a a time and the slow node traverses normally. Now if there is a cycle then the fast pointer will become equal to the slow pointer

int floydCycle(Node* &front)
{
    Node *slow = (Node*)malloc(sizeof(Node));
    Node *fast = (Node*)malloc(sizeof(Node));
    slow=front;
    fast=front;
    while(slow && fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast) return 1;
    }
    return 0;
}

Brent’s Cycle finding algorithm is very different than Floyd’s Algorithm. It is based on finding the smallest power of 2^i. This can be used to calculate the length of the cycle.

int brentCycle(Node* &front)
{
    Node *slow = (Node*)malloc(sizeof(Node));
    Node *fast = (Node*)malloc(sizeof(Node));
    slow=front;
    fast=front;
    int i=0,j=1;
    while(slow!=NULL)
    {
        slow=slow->next;
        i++;
        if(slow==fast) return 1;
        if(i==j)
        {
            fast=slow;
            j*=2;
        }
    }
    return 0;
}

July 8, 2011 Posted by | C++ | , , | Leave a comment

Linked List

Linked List is great topic for interview questions and it helps to practice a lot of questions. Most of these have been taken from geeksfogeeks

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
struct node
{
    int value;
    struct node* next;
};
typedef struct node Node;
void push_back(Node* &front, Node* &rear,int n)
{
    Node *temp = (Node*)malloc(sizeof(Node));
    temp->value=n;
    temp->next=NULL;
    if(rear==NULL)
    {
        rear=temp;
        front=temp;
    }
    else
    {
        rear->next=temp;
        rear=temp;
    }
}
void print(Node* ref)
{
    Node *temp;
    temp=ref;
    while(temp!=NULL)
    {
        printf("%d\n",temp->value);
        temp=temp->next;
    }
}
void push_front(Node* &front, Node* &rear,int n)
{
    Node *temp = (Node*)malloc(sizeof(Node));
    temp->value=n;
    temp->next=NULL;
    if(front==NULL)
    {
        rear=temp;
        front=temp;
    }
    else
    {
        temp->next=front;
        front=temp;
    }
}
int count(Node *ref)
{
    int count=0;
    Node *temp;
    temp=ref;
    while(temp!=NULL)
    {
        count++;
        temp=temp->next;
    }
    return count;
}
void pop_end(Node* &front, Node* &rear)
{
    int value;
    Node *temp,*prev;
    temp=front;
    prev=NULL;
    while(temp!=NULL && temp->next!=NULL)
    {
        prev=temp;
        temp=temp->next;
    }
    if(prev!=NULL)
    {
        prev->next=NULL;
        value=temp->value;
        rear=prev;
    }
    printf("%d deleted\n",value);
    free(temp);
}
void pop_front(Node* &front)
{
    int value;
    Node *temp;
    temp=front;
    value=temp->value;
    front=front->next;
    printf("%d deleted\n",value);
    free(temp);
}
void getNth(Node* &front,int n)
{
    Node *temp;
    temp=front;
    for(int i=0; temp!=NULL && i<n; i++)
    {
        temp=temp->next;
    }
    printf("Value at %d is %d\n",n,temp->value);
}
void deleteList(Node* &current)
{
    Node *temp;
    while(current!=NULL)
    {
        temp=current;
        current=current->next;
        free(temp);
    }
}
void insertNth(Node* &front, Node* &rear,int index,int n)
{
    if(index==0)
    {
        push_front(front,rear,n);
    }
    else
    {
        Node *prev=NULL,*current;
        current=front;
        for(int i=1; current!=NULL; i++)
        {
            if(i==index)
            {
                Node *temp=(Node*)malloc(sizeof(Node));
                temp->value=n;
                temp->next=current->next;
                current->next=temp;
                break;
            }
            current=current->next;
        }
    }
}
void sortedInsert(Node* &front,int n)
{
    Node *temp=(Node*)malloc(sizeof(Node));
    temp->value=n;
    temp->next=NULL;
    if(front==NULL)
    {
        front=temp;
    }
    else if(n< front->value)
    {
        temp->next=front;
        front=temp;
    }
    else
    {
        Node *current=(Node*)malloc(sizeof(Node));
        current=front;
        while(current->next!=NULL && n>current->next->value)current=current->next;
        temp->next=current->next;
        current->next=temp;
    }
}
void removeDuplicatesSorted(Node* &front)
{
    Node *current = (Node*)malloc(sizeof(Node));
    current=front;
    while(current->next!=NULL)
    {
        if(current->value == current->next->value) current->next=current->next->next;
        else current=current->next;
    }
}
Node* search(Node* &front, Node* &rear, int n)
{
    Node *current = (Node*)malloc(sizeof(Node));
    current=front;
    while(current->next!=NULL)
    {
        if(current->value==n) break;
        current=current->next;
    }
    return current;
}
void deleteNode(Node *ref)
{
    Node *current = (Node*)malloc(sizeof(Node));
    ref->value=ref->next->value;
    current=ref->next;
    ref->next=ref->next->next;
    free(current);
}
void printNthFromLast(Node* &front,int index)
{
    Node *ref = (Node*)malloc(sizeof(Node));
    Node *main = (Node*)malloc(sizeof(Node));
    int n=index;
    ref=main=front;
    while(n--)
    {
        if(ref==NULL)
        {
            printf("Invalid location\n");
            break;
        }
        ref=ref->next;
    }
    while(ref!=NULL)
    {
        ref=ref->next;
        main=main->next;
    }
    printf("Node no. %d from last is %d ",index, main->value);
}
void printMiddle(Node* front)
{
    Node *slow = (Node*)malloc(sizeof(Node));
    Node *fast = (Node*)malloc(sizeof(Node));
    slow=front;
    fast=front;
    while(fast->next!=NULL && slow->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    printf("Middle node is %d\n",slow->value);
}
void reverse(Node* &front)
{
    Node *prev = (Node*)malloc(sizeof(Node));
    Node *current = (Node*)malloc(sizeof(Node));
    Node *next = (Node*)malloc(sizeof(Node));
    current=front;
    prev=NULL;
    while(current!=NULL)
    {
        next=current->next;
        current->next=prev;
        prev = current;
        current = next;
    }
    front=prev;
}
void recursiveReverse(Node* &ref)
{
    Node *first = (Node*)malloc(sizeof(Node));
    Node *rest = (Node*)malloc(sizeof(Node));
    if(ref==NULL) return;
    first=ref;
    rest=first->next;
    if(rest==NULL) return;
    recursiveReverse(rest);
    first->next->next=first;
    first->next=NULL;
    ref=rest;
}
void moveToFront(Node* &front)
{
    Node *current = (Node*)malloc(sizeof(Node));
    Node *previous = (Node*)malloc(sizeof(Node));
    current=front;
    previous=NULL;
    while(current->next!=NULL)
    {
        previous = current;
        current = current->next;
    }
    current->next = front;
    previous->next = NULL;
    front = current;
}
void pairWiseSwap(Node* &front)
{
    Node *temp = (Node*)malloc(sizeof(Node));
    temp = front;
    while(temp!=NULL && temp->next!=NULL)
    {
        swap(temp->value,temp->next->value);
        temp = temp->next->next;
    }
}
void recursivePairWiseSwap(Node* &current)
{
    if(current!=NULL && current->next!=NULL)
    {
        swap(current->value,current->next->value);
        recursivePairWiseSwap(current->next->next);
    }
}

July 8, 2011 Posted by | C++, Data Structures | , , | Leave a comment