#ifndef __LINKLSIT_H__
#define __LINKLSIT_H__
class Node{
public:
int data;
Node* next;
Node()
{
next=NULL;
}
Node(int d, Node* n=NULL)
{
data=d;
next=n;
}
};
class LinkList
{
public:
LinkList();
~LinkList();
int IsEmpty()
{
return head==NULL;
}
void AddHead(int);
void AddTail(int);
void display();
int DelateHead();
int DeleteTail();
void DelteteNode(int);
void findkthNode(int k);
void reverseList();
private:
Node *head,*tail;
};
#endif
#include <iostream>
#include <linkList.h>
using namespace std;
LinkList::LinkList(){
tail=head=NULL;
}
LinkList::~LinkList(){
}
void LinkList::AddHead(int val)
{
head=new Node(val,head);
if(tail==NULL)
{
tail=head;
}
}
void LinkList::AddTail(int val)
{
if(tail==NULL)
{
head=tail=new Node(val);
}
else
{
tail->next=new Node(val);
tail=tail->next;
}
}
int LinkList::DelateHead()
{
if(head==NULL)
{
return -1;
}
int val=head->data;
Node* tmp=head;
head=head->next;
delete tmp;
return val;
}
int LinkList::DeleteTail()
{
if(head==NULL)
{
return -1;
}
int val=tail->data;
if(head==tail)
{
delete head;
head=tail=NULL;
}
else{
Node* temp;
for(temp=head;temp->next!=tail;temp=temp->next);
delete tail;
tail=temp;
tail->next=NULL;
}
return val;
}
void LinkList::DelteteNode(int val)
{
if (head != NULL) {
if (head == tail)
{
delete head;
head = tail = NULL;
} else if(val == head->data)
{
Node *temp = head;
head = head->next;
delete temp;
} else
{
Node *pred, *tmp;
for (pred = head, tmp = head->next; tmp != NULL && !(tmp->data == val);pred=pred->next, tmp=tmp->next);
if (tmp != NULL) {
pred->next = tmp->next;
if (tmp == tail) {
tail = pred;
}
delete tmp;
}
}
}
}
void LinkList::display(){
if(head==NULL)
{
cout<<"list is empty"<<endl;
return;
}
Node* cur=head;
while(cur){
cout<<cur->data<<endl;
cur=cur->next;
}
}
void LinkList::findkthNode(int k)
{
if(tail==NULL)
{
return;
}
int len=0;
Node* cur=head;
while(cur){
len++;
cur=cur->next;
}
if(k>len)
{
cout<<"k is lagger than list length"<<endl;\
}
Node* slow=head;
Node* fast=head;
int i=0;
while(head){
if(i<k)
{
fast=fast->next;
i++;
}
else{
slow=slow->next;
fast=fast->next;
}
head=head->next;
}
cout<<slow->data<<endl;
}
void LinkList::reverseList()
{
if(tail==NULL)
return;
Node* cur=head;
Node *pre=NULL;
Node *next;
while(cur)
{
next=cur->next;
if(next==NULL){
head=cur;
}
cur->next=pre;
pre=cur;
cur=next;
}
}
int main(){
LinkList a;
a.AddHead(1);
a.AddTail(2);
a.AddHead(3);
a.AddTail(2);
a.display();
a.reverseList();
}
Processed:
0.011, SQL:
9
