Write an program to count number of nodes in a singly linked list?
int Length(struct node* head) {
int count = 0;
struct node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return(count);
}
Write an efficient C/C++ program to reverse a singly linked list?
Node* ReverseList( Node * List ) {
Node * list1 = List;
Node * revList = NULL;
Node * temp = NULL;
while ( list1 ) {
temp = list1;
list1 = list1->pNext;
temp->pNext = revList;
revList = temp;
}
return revList;
}
Write an efficient C/C++ program to check whether a linked list has a loop
boolean CheckIsItCircular(Node *list) {
Node * list1 = list;
Node * list2 = list;
while(list2) {
list1 = list1 -> next;
list2 = list2 -> next;
if(list2) list2 = list2 -> next;
else return false;
(list1 == list2) ) return true;
}
return false;
}
Detect a Cycle in a linked list and Fix the cycle
How can you find the nodes with repetetive data in a linked list?
void findDuplicates(Node *list) {
Node * first = list;
Node * second;
while (first) {
second = first;
second = second -> next;
while (second) {
if(second
-> data == first -> data) {
print ("%d", second ->data); \\assume data is integer
}
second = second
-> next;
}
first = first -> next;
}
}
Write a function to remove the nodes with repetetive data in a linked list?
void removeDuplicates(Node *list) {
Node * first = list;
Node * second;
Node * pre;
while (first) {
second = first;
pre = first;
second = second -> next;
while (second) {
if(second ->
data == first -> data) {
pre
-> next = second -> next;
print
("%d", second ->data); \\ assume data is integer
free
(second);
second
= pre;
}
pre = second;
second = second
-> next;
}
first = first -> next;
}
}
Write a function to swap every second node. [ie - 1->2->3->4->5->| becomes 2->1->4->3->5->|]
Recursive Method in C++:
List * SwapAlternate(List * head) {
if(head == null) return head;
if(head -> next == null) return head;
List * temp = head->next;
List * temp1 = null;
temp1 = SwapAlternate(head->next->next);
head -> next = temp1;
temp -> next = head;
return temp;
}
Sort a linked list
void Sort( Node *Head) {
node* first,second,temp;
first= Head;
temp = new node();
while(first!=null) {
second=first->NEXT;
while(second!=null) {
if(first->value < second->value) {
temp->value=first->value;
first->value=second->value;
second->value=temp->value;
}
second=second->NEXT;
}
first=first->NEXT;
}
delete temp;
}
Write a function to Insert a node into sorted linked list
void sortedInsert(Node * head, Node* newNode) {
Node *current = head;
Node *pre = NULL;
// traverse the list until you find item bigger the new node value
while (current!= NULL && current->data <newNode->data) {
pre = current;
current = current->next;
}
// insert the new node before the big item
newNode->next = current;
if(pre != NULL)
pre->next = newNode;
else
head = newNode;
}
Write a function to return Nth node from the end of the linked list
Node * GetNthNodeFromEnd ( Node* Head , int N ) {
Node * pthNode = NULL;
Node * tempNode = NULL;
int currentElement = 0;
for ( tempNode = Head; tempNode != NULL; tempNode = tempNode->Next ) {
currentElement++;
if ( currentElement - N == 0 )
pthNode = Head;
else if ( nCurrentElement - N > 0)
pthNode = pthNode ->Next;
}
if (pthNode)
return pthNode;
else
return NULL;
}
Other improved Method
Node * GetNthNodeFromEnd ( Node* Head , int N ) {
Node * temp=Head, *nthNodeFromEnd = NULL;
int i;
for(i=0; i<N-1 && temp; ++i) {
temp = temp->next;
}
if(temp == null) {
return NULL;
}
else {
nthNodeFromEnd = Head;
temp = temp -> next;
}
while(temp) {
nthNodeFromEnd = nthNodeFromEnd->next;
temp = temp->next;
}
return nthNodeFromEnd;
}
|
