Ramayan Tiwari
BAN USERwhile (second !=NULL){
first=first->next;
second=second->next->next;
}
This will cause a segmentation fault, when number of elements in the list are odd. Consider a list only 1 elements and the above code will result in segmentation fault, because the code second->next->next will result in NULL->next.
Here is my solution, works in O(n)
#include <iostream>
using namespace std;
int FindGreatest(int num);
int main(void)
{
int number = 1298349923;
cout<<FindGreatest(number)<<endl;
return 0 ;
}
int FindGreatest(int num)
{
int max = -1;
while(num>1000)
{
long rem = num%10000;
if(rem > max) max = rem;
num /=10;
}
return max;
}
// Program to find the kth last element of a list in O(n) time
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int n)
{
data = n;
next = 0;
}
};
class FindElement
{
public:
Node *start;
FindElement()
{
start = 0;
}
void addNode(int n)
{
// This function always adds node at the beginning, just used to create a demo list
Node *newNode = new Node(n);
if(start==0)
{
start = newNode;
}
else
{
newNode->next = start;
start = newNode;
}
}
int getKthLastElement(int pos)
{
Node *p=start;
Node *q = p;
int i = 1;
//Incrementing p pointer pos times, then we will increment both p and q
while(i<=pos && p!=0)
{
p = p->next;
i++;
}
// Taking care of invalid position inputs
if((i-1)<pos || pos<=0)
{
cerr<<"Invalid value of k\n";
return(-1);
}
// P only traverses the list once
while(p!=0)
{
p = p->next;
q = q->next;
}
return (q->data);
}
void printList()
{
Node *p = start;
while(p!=0)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
};
int main()
{
FindElement list;
int k;
list.addNode(50);
list.addNode(40);
list.addNode(30);
list.addNode(20);
list.addNode(10);
cout<<"Demo List"<<endl;
list.printList();
cout<<endl;
cout<<"Enter the value of k: ";
cin>>k;
int result = list.getKthLastElement(k);
if(result!=-1)
cout<<"\n"<<k<<"th value from the end of the list is "<<result<<endl;
return 0;
}
Hey
Nice logic to implement this, I liked it as its very general.
I doesn't give correct answer though
For input sample, "1234" with operators "+" and "-", it only results in 22 samples, whereas the actual samples are 26, it dint generate 1+23-4, 1+23+4, 1-23-4 and 1-23+4.
The below code uses two pointer strategy and checks for Palindrome Lists. It is also using C++ template mechanism to make it more general.
- Ramayan Tiwari February 04, 2012