struct node *reverse(struct node **head)
{
struct node *curr=*head;
struct node *prev=NULL;
truct node *next;
while(curr!=NULL)
{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
return prev;
}
struct node *segregateEvenOdd(struct node **head_ref)
{
struct node *curr = *head_ref;
struct node *even=NULL,*odd=NULL,*evenh,*oddh;
while(curr!=NULL)
{
if(curr->data%2==0)
{
push(&even,curr->data);
}
else
{
push(&odd,curr->data);
}
curr=curr->next;
}
evenh=reverse(&even);
struct node *temp=evenh;
oddh=reverse(&odd);
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=oddh;
return evenh;
}
Category Archives: DS
Reverse stack
void rev_stack(Stack <Integer> s)
{
if( !s.isEmpty() ) return;
int temp = s.pop();
rev_stack(s);
insert_at_bottom(s, temp);
}
public void insert_at_bottom(Stack <Integer> s, int data)
{
if (!s.isEmpty()){
s.push(data);
return;
}
int temp1=s.pop();
insert_at_bottom(s);
s.push(temp1);
}
Sort Stack
public void sort(Stack<Integer> s){
int x=0;
if (!s.isEmpty()){
x=s.pop();
sort(s);
insert(s,x);
}
}
public void insert(Stack<Integer> s, int x){
if (!s.isEmpty() && s.peek()>= x){
int y=s.pop();
insert(s, x);
s.push(y);
}
else {
s.push(x);
}
}
Largest Rectangular Area in a Histogram
int getMaxArea(int hist[], int n){ stack<int> s; int max_area = 0; int tp; // To store top of stack int area_with_top; int i = 0; while (i < n) { // If this bar is higher than the bar on top stack, push it to stack if (s.empty() || hist[s.top()] <= hist[i]) s.push(i++); // If this bar is lower than top of stack, then calculate area of rectangle // with stack top as the smallest (or minimum height) bar.
else { tp = s.top(); // store the top index s.pop(); // pop the top // Calculate the area with hist[tp] stack as smallest bar area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); if (max_area < area_with_top) max_area = area_with_top; } } // Now pop the remaining bars from stack and calculate area with every // popped bar as the smallest bar while (s.empty() == false) { tp = s.top(); s.pop(); area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); if (max_area < area_with_top) max_area = area_with_top; } return max_area;}Reverse alternate K nodes in a Singly Linked List
Example:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3 Output: 3->2->1->4->5->6->9->8->7->NULL.
Algo
kAltReverse(struct node *head, int k) 1) Reverse first k nodes. 2) In the modified list head points to the kth node. So change next of head to (k+1)th node 3) Move the current pointer to skip next k nodes. 4) Call the kAltReverse() recursively for rest of the n - 2k nodes. 5) Return new head of the list.
Code
struct node *kAltReverse(struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if(head != NULL)
head->next = current;
count = 0;
while(count < k-1 && current != NULL )
{
current = current->next;
count++;
}
if(current != NULL)
current->next = kAltReverse(current->next, k);
Reverse a Linked List in groups of given size
Given a linked list, write a function to reverse every k nodes (where k is an input to the function).
Example:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL.
Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5
Output: 5->4->3->2->1->8->7->6->NULL.
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next = NULL;
struct node* prev = NULL;
int count = 0;
/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if(next != NULL)
{ head->next = reverse(next, k); }
/* prev is new head of the input list */
return prev;
}
Reverse a linked list
Iterative Method
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
Recursive Method
let’s say we are dealing with node 99 in the linked list image above – the Node coming after node 99 (node 37) is represented by Node 99 -> next. If we want node 37 to point back to node 99 (which is what we would want if we are reversing the nodes), then we would set the next pointer of node 37 to point back to Node 99, which in pseudocode would look like Node99 -> next -> next = Node 99.
We would also need to get rid of the pointer from node 99 to node 37 so we would have to set Node 99 -> next to NULL.
CODE
public void recursiveReverse(Node currentNode )
{
if(currentNode == NULL)
return;
if(currentNode.next == NULL)
{
head = currentNode;
return;
}
recursiveReverse(currentNode.next);
currentNode.next.next = currentNode;
currentNode.next = null; //set "old" next pointer to NULL
}
Learn By Coding 