单向链表是微软笔试常考的，参考这里：http://www.cnblogs.com/tdyizhen1314/archive/2012/04/03/2431124.html
#include<iostream>
using namespace std;
struct node{
int data;
struct node* next;
};
//定义一个名字呢
node* create(unsigned int n){
if(n==0){
cout<<"ensure n>0. (create failure)"<<endl;
return NULL;
}
//assert(n>0);
node* head=new node;//new一个struct
cout<<"#1:";
cin>>head->data;
head->next=NULL;
int i;
node *pre=head;
node *cur=NULL;
for(i=1;i<n;i++){
cur=new node;
cout<<"#"<<i+1<<":";
cin>>cur->data;
cur->next=NULL;
pre->next=cur;
pre=cur;
}
return head;
}
/*
丑方法：
node* reverse(node* list){
node* one=list;
node* two=NULL;
node* three=NULL;
if(list->next!=NULL)
two=list->next;
else
return list;
if(list->next->next!=NULL)
three=list->next->next;
one->next=NULL;
while(two!=NULL){
two->next=one;
one=two;
two=three;
if(three!=NULL)
three=three->next;
else
break;
}
return one;
}
*/
/*问题1：链表反转
思路：head指针不断后移，指针反向即可
*/
void reverse(node*& head){
/*1. 先讨论空链表和只有一个节点的情况*/
if(head==NULL)
return;
if(head->next==NULL)
return;
/*2. 在处理普通情况*/
node* p=head;
node* q=head->next;
while(q!=NULL){
node* temp=q->next;
q->next=p;
p=q;
q=temp;
}
head->next=NULL; //反转前的链表头特殊处理
head=p;
}
/*问题2：删除不知头结点链表的某个节点
如果单向链表不知道头节点，一个指针指向其中的一个节点，问如何删除这个指针指向的节点
思路：下一个节点的值复制给该节点，然后删除下一个节点即可
*/
void deleteNodeInList(node*& n){
if(n==NULL)
return;
if(n->next==NULL){
delete n;
n=NULL;
return;
}
/*一般情况：存在下一个节点*/
node* nextNode=n->next;
n->data=nextNode->data;
n->next=nextNode->next;
delete nextNode;
}
/*
问题3：判断链表中是否有环
思路：
设置两个指针，一个步长为1，另一个步长为2，依次后移，如果相遇且都不为空，则有环。
解释：
que:
跑步能追上确实很容易理解。但问题是，跑步是连续的，而这里不是。因为有一个指针是跳两步的，不是连续的，怎么证明这样也肯定能碰上；好像只能证明一定能超过啊
ans:
画上一个圈就知道啦!速度快的开始肯定会超过慢的.
一个步长1（乌龟），另外一个步长2（兔子），因此兔子一次追上1个单位,如果确实是个圈的话肯定会追上并且是相遇在同一个单位之内!
*/
node* hasLoop(node* head){ //返回第一次交汇的点（能写成输入参数吗）
if(head==NULL)
return NULL;
if(head->next==NULL)
return NULL;
/*至少有2个节点的单链表*/
node* p=head;
node* q=head;
while(true){
if(p==NULL || q==NULL)
return NULL;
if(p->next==NULL || q->next==NULL)
return NULL;
if(q->next->next==NULL)
return NULL;
//p步长为1后移
p=p->next;
//q步长为2后移
q=q->next->next;
//如果p,q重合在非NULL节点，则有环
if(p==q && p!=NULL){
return p;
}
}
}
/*
问题4：找出环的入口节点
思路：
当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。
假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：
2s = s + nr <==> s= nr
设入口环与相遇点距离为x，x<r，起点到环入口点的距离为a.
a = s - x = (n-1)r+ (r-x), 而r-x即为fast再次到环入口点时的步数
由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
*/
node* getLoopHead(node* list){
node* inter; //第一次交汇点
if( (inter=hasLoop(list)) !=NULL ){
node* p=list;
while(true){
if(p==inter)
return p;
p=p->next;
inter=inter->next;
}
}
return NULL;
}
/*
问题5：找出倒数第k个节点
*/
node* findLastK(node* head, unsigned int k){
/*
back指向开始处, front指向前于它(k-1)个位置处
*/
node* back=head;
node* front=head;
for(int i=1;i<k;i++){
if(front==NULL)
return NULL;
front=front->next;
}
if(front==NULL)
return NULL;
/*
后移
*/
while(front->next){
back=back->next;
front=front->next;
}
return back;
}
/*
问题6： 《编程之美》 3.6 判断两个链表是否相交
*/
void traverse(node* list){
node* p=list;
while(p!=NULL){
cout<<p->data<<"\t";
p=p->next;
}
cout<<endl;
}
int main(){
cout<<"****************创建****************"<<endl;
node* list=create(6);
traverse(list);
/*
cout<<"****************反转****************"<<endl;
reverse(list);
traverse(list);
node* list2=create(2);
traverse(list2);
reverse(list2);
traverse(list2);
node* list3=create(1);
traverse(list3);
reverse(list3);
traverse(list3);
node* list4=create(0);
cout<<"****************删除孤立节点****************"<<endl;
deleteNodeInList(list->next->next);
traverse(list);
cout<<"**************** 检测环 | 找出环的入口节点 ****************"<<endl;
if(hasLoop(list)==NULL)
cout<<"无环"<<endl;
else
cout<<"有环"<<endl;
//奇数(3)长度环
node* n1=new node;
node* n2=new node;
node* n3=new node;
node* n4=new node;
n1->data=1;
n2->data=2;
n3->data=3;
n4->data=4;
n1->next=n2;
n2->next=n3;
n3->next=n4;
n4->next=n2;
if(hasLoop(n1)==NULL)
cout<<"无环"<<endl;
else
cout<<"有环"<<endl;
node* inter=getLoopHead(n1);
cout<<"环入口: "<<inter->data<<endl;
delete n1;
delete n2;
delete n3;
delete n4;
//偶(2)长度环
n1=new node;
n2=new node;
n3=new node;
n4=new node;
n1->data=1;
n2->data=2;
n3->data=3;
n4->data=4;
n1->next=n2;
n2->next=n3;
n3->next=n4;
n4->next=n3;
if(hasLoop(n1)==NULL)
cout<<"无环"<<endl;
else
cout<<"有环"<<endl;
inter=getLoopHead(n1);
cout<<"环入口: "<<inter->data<<endl;
delete n1;
delete n2;
delete n3;
delete n4;
*/
cout<<"****************寻找倒数第k个节点****************"<<endl;
node* last0=findLastK(list,0);
cout<<last0->data<<endl;
node* last1=findLastK(list,1);
cout<<last1->data<<endl;
node* last3=findLastK(list,3);
cout<<last3->data<<endl;
node* last4=findLastK(list,4);
cout<<last4->data<<endl;
system("pause");
return 0;
}
相关推荐
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 2．遍历单向链表。 3．把单向链表中元素逆置（不允许申请新的结点空间）。 4．在单向链表中删除所有的偶数元素结点。 5．编写在非递减...
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码
c++实现单向链表逆转，c++实现单向链表逆转，c++实现单向链表逆转，c++实现单向链表逆转，c++实现单向链表逆转，
单向链表架构代码，适合学习链表的学生学习！内附排序函数，打印函数，链表尾添项函数，删除函数。
这是一个单向链表，它具有插入与删除节点的功能。Entry类实现了链表的各节点。
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
将一个单向链表反向连接
本文件描述单向链表类模板。移植时，仅需要本文件
培训班老师自己写的单向链表，代码非常全，也很好理解，可执行。
单向链表类定义及测试文件 对应于数据机构与算法分析（c++版）第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
数据结构，c语言实现的单向链表。代码分享 struct LinkNode { int data; struct LinkNode *next; }; typedef struct LinkNode *Lnode;
C++进阶学习——单向链表的实现,相关教程链接如下： http://blog.csdn.net/tennysonsky/article/details/49685199
java语言模拟单向链表,JAVA数据结构
C 语言版 单向链表 #include #include typedef struct student { int num; struct student *next; }st; st *creat() //创建链表 { st *head , *tail , *p; int num = 0; head = tail = p = NULL; printf...
slist.h为单向链表，blist为双向链表
数据结构实验报告，使用vC++ 6.0工具来进行调试单向链表。
很好的一个说明了单向链表的操作方法 创建
该代码给出了单向链表的一系列操作，如节点插入，节点删除，反序排列单向链表中的所有节点，统计单向链表中节点的个数，在链表中查找给定的节点，遍历链表等一系列操作。 声明：该代码参考了《C和指针》，对其中的...