Simple C Program to get the kth node from last in a linked list

This can be done in single traversal using two pointers . First move to the kth node from first and point it using temp pointer . Point the head node using another pointer called kthnodefromlast .Now Move the temp pointer and kthnodefromlast to next node till temp node reaches the end of the linked list.

Example:

 1->2->3->4->5->6->7->NULL

 For the above linked list kth(k=3) node from last is 5.

 Code:(in C)

	struct node* getKthNodeFromLast(struct node* head , int k)
	{
	if(head==null || k<1)
	return null;
	struct node* temp=head,*kthnodefromlast=head;
	while(--k>0)
	{
	temp=temp->link;
	if(temp==null)
	return null;
	}
	while((temp=temp->link)!=null)
	kthnodefromlast=kthnodefromlast->link;
	return kthnodefromlast;
	}

view raw kthfromlast.c hosted with ❤ by GitHub

Time Complexity : O(n)
Space Complexity: O(1)

 Please let me know if you have any questions .

C Program to swap kth node from first and kth node from last in a Linked List

Consider you have the following linked list and you want to swap second node from first and second node from last .

The steps are given below .

     1)Get the size of the linked list . If the size is less than k you can't swap the element . And in the above linked list if k value is 3 you dont need to swap the element .
     2)The two pointers kthnodefromfirst and kthnodefromlast used to point the nodes that we need to swap and its previous nodes are pointed using previous1,previous2.
     3)swap the two nodes . And while swapping you need to check whether you are swapping the head or not . Its one of the important test case .

Code:(in C)

	//Swap kth node from first and last
	struct node * swapKthNode(struct node * head,int k)
	{
	if(head==null)
	return null;
	int size=size_of_linkedlist(struct node* head);
	if(size<k || k==size-k+1)
	return head;
	int i=k,j=size-k+1;
	if(i<j)
	head=swap(head,i,j);
	else
	head=swap(head,j,i);
	return head;
	}
	struct node * swap(struct node * head,int i,int j)
	{
	struct node* kthnodefromfirst=head,kthnodefromlast,previous1=null,previous2,temp;
	while(--i > 0)
	{
	previous1=kthnodefromfirst;
	kthnodefromfirst=kthnodefromfirst->link;
	}
	j=j-i;
	kthnodefromlast=kthnodefromfirst;
	while(j-- > 0)
	{
	previous2=kthnodefromlast;
	kthnodefromlast=kthnodefromlast->link;
	}
	//swap the two nodes
	temp=kthnodefromfirst->link
	kthnodefromfirst->link=kthnodefromlast->link;
	kthnodefromlast->link=temp;
	previous2->link=kthnodefromfirst;
	if(previous1==null)
	head=kthnodefromlast;
	else
	previous1->link=kthnodefromlast;
	return head;
	}

view raw swapkth.c hosted with ❤ by GitHub

Time Complexity : O(n)
Space Complexity: O(1)

Please let me know if you have any questions .

Simple C Program to check whether the given Binary Tree is Binary Search Tree or not

This can be done in many ways . The simplest way is by using the Inorder Traversal . If we traverse a binary search tree using inorder traversal all the elements are in sorted order .

For the above binary search tree Inorder traversal is

 1  2  3  4  5  6  7

In the following code flag is used like a boolean varible . In the Inorder traversal if the elements are not in sorted order flag is set to 0 . The variable 'min' is used to store the previous value in inorder traversal . Initially it is assigned to the mininum integer value possible which is -32768.

Code :(in C)

	void CheckBST(struct node* root)
	{
	int flag=1,min=-32768;
	if(root==null)
	{
	printf("Empty Tree");
	return;
	}
	IsBst(root,&min,&flag);
	if(flag==1)
	printf("Binary Search Tree");
	else
	printf("Not a Binary Search Tree");
	}
	void IsBst(struct node* node,int *min,int *flag)
	{
	if(node!=null)
	{
	IsBst(node->left,min,flag);
	if(node->data < *min)
	{
	*flag=0;
	return;
	}
	else
	*min=node->data;
	IsBst(node->right,min,flag);
	}
	}

view raw isbst.c hosted with ❤ by GitHub

Please let me know if you have any questions .