Linked List Collection
/*
Intersection of two Sorted Linked Lists
Given two lists sorted in increasing order, create and return
a new list representing the intersection of the two lists.
The new list should be made with its own memory — the
original lists should not be changed.
For example, let the first linked list be 1->2->3->4->6
and second linked list be 2->4->6->8, then your function should create
and
return a third list as 2->4->6.
*/
node*
sortedIntersect(node* a, node* b)
{
if (a ==
NULL||b == NULL)
{
return
(NULL);
}
if
(a->data <b->data)
{
return
sortedIntersect(a->next, b);
}
if
(a->data >b->data)
{
return
sortedIntersect(a, b->next);
}
node* temp = (node*)malloc(sizeof(node));
temp->data = a->data;
temp->next =
sortedIntersect(a->next, b->next);
return
temp;
}
/* Link list node */
struct Node
{
int data;
struct
Node* next;
};
typedef struct
Node node;
/* Given a reference (pointer to pointer) to the head
of a list and an int,
push a new node on the front
of the list. */
void push(struct
Node** head_ref, int new_data)
{
struct
Node* new_node =
(struct
Node*) malloc(sizeof(struct
Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Drier program to test count function*/
int main()
{
/* Start with the
empty list */
struct
Node* head1 = NULL;
/* Use push() to
construct below list
1->2->3->4->5 */
push(&head1, 6);
push(&head1, 4);
push(&head1, 3);
push(&head1, 2);
push(&head1, 1);
struct
Node* head2 = NULL;
push(&head2, 8);
push(&head2, 6);
push(&head2, 4);
push(&head2, 2);
node*temp = sortedIntersect(head1, head2);
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp = temp->next;
}
getchar();
return 0;
}
/* Link list node */
struct Node
{
int data;
struct
Node* next;
};
/* Given a reference (pointer to pointer) to the head
of a list and an int,
push a new node on the front
of the list. */
void push(struct
Node** head_ref, int new_data)
{
struct
Node* new_node =
(struct
Node*) malloc(sizeof(struct
Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Counts no. of nodes in linked list */
int getCount(struct
Node* head)
{
int count =
0; //
Initialize count
struct
Node* current = head; // Initialize current
while
(current != NULL)
{
count++;
current = current->next;
}
return
count;
}
/* Takes head pointer of the linked list and index
as arguments and
return data at index*/
int getNth(struct
Node* head, int n)
{
struct
Node* curr = head;
for (int i=0; i<n-1 && curr != NULL; i++)
curr = curr->next;
return curr->data;
}
/*
Printing the data in
reverse order using stack
*/
void printReverse(Node *head)
{
// store Node
addresses in stack
stack<Node *> stk;
Node* ptr = head;
while (ptr
!= NULL)
{
stk.push(ptr);
ptr = ptr->next;
}
// print data
from stack
while
(!stk.empty())
{
cout << stk.top()->data
<< " ";
stk.pop(); //
pop after print
}
cout << "\n";
}
/*
Reverse a linked list using a recurssion
*/
void reverse(struct
Node **headref)
{
struct
Node *first;
struct
Node *rest;
first = *headref;
rest = first->next;
if (first
== NULL ||rest == NULL)
{
return;
}
reverse(&rest);
first->next->next = first;
first->next = NULL;
*headref = rest;
}
/* Drier program to test count function*/
int main()
{
/* Start with the
empty list */
struct
Node* head = NULL;
/* Use push() to
construct below list
1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
//printReverse(head);
reverse(&head);
struct
Node *temp = head;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp = temp->next;
}
getchar();
return 0;
}
Comments
Post a Comment