Simple solutions for complex problems on single linked list..

Discussion in 'C' started by dharmaraj.guru, Nov 6, 2007.

  1. dharmaraj.guru

    dharmaraj.guru New Member

    Joined:
    Oct 23, 2007
    Messages:
    16
    Likes Received:
    0
    Trophy Points:
    0
    Listed here are few common complex operations of single linked list that is to be needed by certain applications. These operations should be done in single traversal for improved performance.

    Here are few of them and their solutions..

    1. Reverse the list.
    2. Find n-th node from tail end.
    3. Find middle node of the list.
    4. Delete a node whose address is known, without having the head node's address.

    1. Reverse the list
    Logic :
    a. Get each node from front end till last.
    b. Add them into another list at front.​

    2. Find n-th node from tail end.
    a. Have two pointers pointer1 and pointer2.
    b. Point all of them to head initilally.
    c. Move only pointer1 for n nodes.
    d. Move both pointers for the rest nodes of list.
    e. At the end of traversal, pointer2 will be pointing to n-th node from tail.​

    3. Find middle node of the list.
    a. Have two pointers pointer1 and pointer2.
    b. Point all of them to head initilally.
    c. Move only pointer1 by one node.
    d. Move pointer2 by two nodes till the end of list.
    e. At the end of traversal, pointer1 will be pointing to middle node from tail.​

    4. Delete a node without having the head node's address
    a. copy the contents of next node's data to current node's data.
    b.Store the next node's next node at current node's link.​

    In all cases, we have to take care of boundary conditions as well as memory leaks.
    Here is the code..

    Code:
    #include <stdio.h>
    
    struct node
    {
    	int data;
    	struct node* next;
    };
    
    // Functions for allocating/deallocating memory
    struct node* create_node(int data);
    
    // Utility functions that can be used in reverse_list
    struct node* insert_at_front(struct node* head, struct node* new_node);
    struct node* insert_at_end(struct node* head, struct node* new_node);
    
    struct node* remove_from_front(struct node* head);
    struct node* reverse_list(struct node* head);
    
    // Delete a node without having the head pointer..
    void delete_this_node(struct node* cur_node);
    
    // Find nth node from tail in single traversal..
    struct node* find_nth_from_end(struct node* head, int n);
    
    // Find middle node of the list in single traversal..
    struct node* find_middle_node(struct node* head);
    
    // Dump the list/node..
    void dump_list(struct node* head);
    void dump_node(struct node* pNode);
    void copy_node(struct node* src, struct node* dest);
    
    // Main function
    int main(void)
    {
    	struct node *list = NULL, *temp_node = NULL;
    	int i = 0;
    
    // Create list with 10 members...
    	for(i = 0; i <= 10; i++) {
    		temp_node = create_node(i);
    		list = insert_at_end(list, temp_node);
    	}
    
    // Add 5 more in front...
    	for(i = 14; i >= 11; i--) {
    		temp_node = create_node(i);
    		list = insert_at_front(list, temp_node);
    	}
    
    	dump_list(list);
    
    // To reverse a single linked list in single traversal.......
    /*
    	list = reverse_list(list);
    */
    
    // Delete a particular node without having the head pointer
    /*
    	temp_node = list;
    
    	for(i = 0; i <= 15; i++) {
    
    		if(i == 4) {
    			delete_this_node(temp_node);
    			break;
    		}
    
    		temp_node = temp_node->next;
    	}
    	dump_list(list);
    */
    
    // To find nth node from the end of list in single traversal....
    /*
    	temp_node = find_nth_from_end(list, 10);
    
    	dump_node(temp_node);
    */
    
    // To find the middle node of list in single traversal......
    
    /*
    	temp_node = find_middle_node(list);
    
    	dump_node(temp_node);
    
    	list = reverse_list(list);
    
    	dump_list(list);
    
    	temp_node = find_middle_node(list);
    
    	dump_node(temp_node);
    */
    	return 0;
    }
    
    // Allocate memory and store the data
    struct node* create_node(int data)
    {
    	struct node *new_node = NULL;
    
    	new_node = (struct node*)malloc(sizeof(struct node));
    
    	new_node->data = data;
    	new_node->next = NULL;
    
    	return new_node;
    }
    
    // Deallocate the memory
    void free_this_node(struct node* pNode)
    {
    	free(pNode);
    	pNode = NULL;
    
    	return;
    }
    
    // Insert a node at front end
    struct node* insert_at_front(struct node* head, struct node* new_node)
    {
    	if(new_node) {
    		new_node->next = head;
    		return new_node;
    	}
    	else
    		return NULL;
    }
    
    // Insert a node at tail end
    struct node* insert_at_end(struct node* head, struct node* new_node)
    {
    	struct node *temp = NULL;
    
    	if(head) {
    
    		temp = head;
    
    		while(temp->next)
    			temp = temp->next;
    
    		temp->next = new_node;
    	}
    	else {
    		head = new_node;
    	}
    
    	return head;
    }
    
    // Remove a node from front end..
    struct node* remove_from_front(struct node* head)
    {
    	if(head) {
    		head = head->next;
    		return head;
    	}
    	else
    		return NULL;
    }
    
    // Reverse the list in single traversal..
    struct node* reverse_list(struct node* head)
    {
    	struct node *result = NULL, *temp_head = NULL, *temp = NULL;
    
    	temp_head = head;
    
    	while(temp_head) {
    
    		temp = temp_head;
    
    		temp_head = remove_from_front(temp_head);
    
    		temp->next = NULL;
    	
    		result = insert_at_front(result, temp);
    	}
    
    	return result;
    }
    
    // Delete a node without the help of head node..
    void delete_this_node(struct node* cur_node)
    {
    	struct node *temp = NULL;
    	if(cur_node && cur_node->next) {
    
    		copy_node(cur_node, cur_node->next);
    		temp = cur_node->next;
    		cur_node->next = cur_node->next->next;
    
    		free_this_node(temp);
    	}
    	else if(cur_node) {
    		free_this_node(cur_node);
    	}
    	else
    		return;
    }
    
    // Find n-th node from tail end in single traversal...
    struct node* find_nth_from_end(struct node *head, int n)
    {
    	struct node *temp = NULL, *result = NULL, *temp_head = NULL;
    	int i = 0;
    
    	result = temp_head = temp = head;
    
    	for(i = 0; i < n; i++) {
    		if(!temp_head) {
    			printf("Out of Range\n");
    			return NULL;
    		}
    		temp_head = temp_head->next;
    		temp = temp->next;
    	}
    
    	while(temp_head) {
    		temp_head = temp_head->next;
    		temp = temp->next;
    		result = result->next;
    	}
    
    	return result;
    }
    
    // Find middle node of list in single traversal...
    struct node* find_middle_node(struct node* head)
    {
    	struct node *temp_head = NULL, *temp = NULL, *result = NULL;
    
    	temp_head = temp = result = head;
    
    	while(temp && temp->next) {
    
    		if(temp->next->next) {
    			temp = temp->next->next;
    			result = result->next;
    		}
    		else 
    			temp = temp->next;
    	}
    
    	return result;
    }
    
    // Dump the list...
    void dump_list(struct node* head)
    {
    	struct node *temp = NULL;
    
    	printf("\n");
    
    	if(head) {
    
    		temp = head;
    
    		while(temp) {
    			printf("%d ", temp->data);
    			temp = temp->next;
    		}
    	}
    	else {
    		printf("Empty List");
    	}
    
    	printf("\n");
    }
    
    // Copy data in b/w two nodes...
    void copy_node(struct node* src, struct node* dest)
    {
    	src->data = dest->data;
    
    	return;
    }
    
    // Dump a node
    void dump_node(struct node* pNode)
    {
    	if(pNode)
    		printf("\nNode details : Addr : %x, data : %d\n", pNode, pNode->data);
    	else
    		printf("\n Node is NULL \n");
    
    	return;
    }
    
    Uncomment the relevant snippet from main for testing it.
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  3. rc410

    rc410 New Member

    Joined:
    Nov 30, 2007
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Well this is good program
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  5. ducuytran

    ducuytran Banned

    Joined:
    Dec 16, 2007
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    Location:
    Ác Nhân Cốc
    Home Page:
    http://www.quaacdoc.com
    SO Great! It's a part of my syllabus. Thank you, thankz so much!
     
  6. strsub

    strsub New Member

    Joined:
    Aug 30, 2007
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Location:
    indonesia
    :D very interesting
     
  7. mr.anandc

    mr.anandc New Member

    Joined:
    May 6, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Interesting.. very simple solutions...
     
  8. vijay_visana

    vijay_visana New Member

    Joined:
    Aug 3, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    System Analyst
    Location:
    Uk
    here is one more way to reverse singly linked list
    PNODE revLinkList(PNODE pNode,PNODE prevNode)
    {
    PNODE pTop = NULL;
    if( pNode->next)
    pTop = revLinkList(pNode->next,pNode);
    else
    pTop = pNode;
    pNode->next=prevNode;
    return pTop;
    }

    one more question
    how to reverse block in singly linked list
    like
    1->2->3->4->5->6->7->8->9->10->11->12
    let us take block size as 3
    so reversed list should be like this
    3->2->1->6->5->4->9->8->7->12->11->10

    vijay
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice