#include  <stdio.h>
#include  <stdlib.h>
/*链表，在表头插入数据，使用了一个头结点head专门记录表头位置*/
typedef struct node
{
	int key;
	struct node *Next;
}Node;
void Insert(int num,Node *head)//插入新的节点 
{
	Node *p = NULL;
	p = (Node *) malloc (sizeof(Node));//开辟新的节点 
 	p->key = num;//赋值 
	p->Next=head->Next;//将原来的头结点挂在新节点后，并把新节点挂在表头上 
	head->Next=p;
}
void Print_List(Node *head)
{
	Node *p = head->Next;
	while(p != NULL)//遍历打印节点值 
	{
		printf("%d->", p->key);
		p = p->Next;
	}
	printf("\n");
}
Node *Search_List(Node *head,int num)//寻找值为num的节点，并返回位置指针 
{
     Node *p=NULL; p=head;
     while((p->Next!=NULL)&&p->key!=num)
         p=p->Next;
     if(p->Next==NULL)
     {
          printf("不存在值为%d的节点,将返回头结点",num);
          return head;
     }
     return p;     
     
} 
void Delete_List(Node *head,int num)//删除值为num的节点
{
     Node *p=NULL; p=head;
     Node *pf=NULL;//记录p的前节点 
     while((p->Next!=NULL)&&p->key!=num)
     {
         pf=p;
         p=p->Next;
     }
     if(p->Next==NULL&&p->key!=num)
          printf("不存在值为%d的节点",num);
     else
     {
         pf->Next=p->Next;
     }
} 
int main()
{	
	int i;
	Node *p=NULL;
	Node *head = (Node *)malloc(sizeof(Node));
	head->Next = NULL;//建立空表头 
	for (i=0; i<10; i++)
	{
		Insert(i, head);
	}
	Print_List(head);
	printf("输入你要查找的值:");
	scanf("%d",&i);
	p=Search_List(head,i);
	printf("已查到节点,值为:%d",p->key); 
	printf("输入你要删除的值:");
	scanf("%d",&i);
	Delete_List(head,i);
	printf("删除以后\n");
	Print_List(head);
	system("PAUSE");
	return 0;
}

最近在linux了一个简单的单向链表，直接上代码
 
链表头文件   list.h
 
#ifndef _LIST_H_
 #define _LIST_H_
 
 typedef int T;
 
 template<typename T>
 class List
 {
 private:
     struct Node
     {
         T      data;
         Node*  next;
         Node(const T& d=T()):data(d),next(NULL){} //零初始化
     };
     Node* head;//头指针,用来保存头节点的地址
     int len;
 public:
     List():head(NULL),len(0){}
     List(const List& l);
     void operator=(const List& l);
     ~List();
     T getElementAtIndex(int index)const;//取得链表中指定位置的元素值
     List<T>& push_front(const T& d);//前插
     List<T>& push_back(const T& d); //尾插
     int size()const;//获取链表中节点个数
     Node*& getptr(int pos); //在链表中找指向指定位置的指针
     List<T>& insert(const T& d,int pos); //在任意位置插入
     void travel()const; //遍历
     void clear(); //清空链表
     void erase(int pos); //删除链表中指定位置的元素
     int find(const T& d)const; //查找指定数值的元素在链表中出现的位置
     void remove(const T& d); //删除链表中指定的元素
     void set(int pos,const T& d);
     bool empty()const;
     const T& front()const;
     const T& back()const;
     void reverse();//链表元素倒置
 };
 
 #endif
 
 
链表实现文件 list.cpp
 
#include <iostream>
 #include <string>
 #include "list.h"
 
 using namespace std;
 
 template<typename T>
 List<T>::List(const List<T>& l)
 {
     len = l.len;
     Node* items[len];
     for(int i=0;i<len;i++)
     {
         items[i] = new Node(l.getElementAtIndex(i));
     }
     for(int i=0;i<len-1;i++)
     {
         items[i]->next = items[i+1];
     }
     head = items[0];
 }
 
 template<typename T>
 void List<T>::operator=(const List<T>& l)
 {
     clear();    
     len = l.len;
     Node* items[len];
     for(int i=0;i<len;i++)
     {
         items[i] = new Node(l.getElementAtIndex(i));
     }
     for(int i=0;i<len-1;i++)
     {
         items[i]->next = items[i+1];
     }
     head = items[0];
 }
 
 template<typename T>
 List<T>::~List()
 {
     clear();
 }
 
 //取得链表中指定位置的元素值
 template<typename T>
 T List<T>::getElementAtIndex(int index)const  
 { 
     if(index < 0 || index >= len) throw "索引位置越界";
     if(index == 0) return head->data;
     Node* p = head;
     for(int i=1;i<index;i++)
     {
         p = p->next;
     }
     return p->next->data;
 }
 
 //前插
 template<typename T>
 List<T>& List<T>::push_front(const T& d)
 {
     insert(d,0);
     return *this;
 }
 
 //后插
 template<typename T>
 List<T>& List<T>::push_back(const T& d)
 {
     insert(d,len);
     return *this;
 }
 
 //获取链表中节点个数
 template<typename T>
 int List<T>::size()const
 {
     return len;
 }
     
 //在链表中找指向指定位置的指针
 template<typename T>
 typename List<T>::Node*& List<T>::getptr(int pos)
 {
     if(pos < 0 || pos > len) pos = 0;
     if(pos == 0) return head;
     Node* p = head;
     for(int i=1;i<pos;i++)
     {
         p = p->next;
     }
     return p->next;
 }
 
 //在任意位置插入节点
 template<typename T>
 List<T>& List<T>::insert(const T& d,int pos)
 {
     Node*& pn = getptr(pos);
     Node* p = new Node(d);
     p->next = pn;
     pn = p;
     ++len;
     return *this;
 }
 
 //遍历
 template<typename T>
 void List<T>::travel()const
 {
     Node* p = head;
     while(p)
     {
         cout << p->data << ' ';
         p = p->next;
     }
     cout << endl;
 }
 
 //清空链表
 template<typename T>
 void List<T>::clear()
 {
     while(head)
     {
         Node* p = head->next;
         delete head;
         head = p;
     }
     len = 0;
 }
     
 //删除链表中指定位置的节点
 template<typename T>
 void List<T>::erase(int pos)
 {
     if(pos < 0 || pos >= len) return;//有效位置为0~len-1
     Node*& pn = getptr(pos);
     Node* p = pn;
     pn = pn->next;
     delete p;
     --len;
 }
 
 //查找指定数值的节点在链表中出现的位置
 template<typename T>
 int List<T>::find(const T& d)const
 {
     Node* p = head;
     int pos = 0;
     while(p)
     {
         if(p->data == d)
           return pos;
         else
           p = p->next;
         ++pos;
     }
     return -1;
 }
     
 //删除链表中指定数值的节点
 template<typename T>
 void List<T>::remove(const T& d)
 {
     int pos;
     while((pos = find(d))!= -1)
     {
         erase(pos);
     }
 }
 
 //修改指定位置的节点数据
 template<typename T>
 void List<T>::set(int pos,const T& d)
 {
     if(pos < 0 || pos >= len) return;
     getptr(pos)->data = d;
 }
 
 //判断链表是否为空
 template<typename T>
 bool List<T>::empty()const
 {
     return head == NULL;
 }
 
 //取得链表中第一个节点数据
 template<typename T>
 const T& List<T>::front()const
 {
     if(empty()) throw "空";
     return head->data;
 }
 
 //取得链表中最后一个节点数据
 template<typename T>
 const T& List<T>::back()const
 {
     if(empty()) throw "空";
     Node* p = head;
     while(p->next)
     {
         p = p->next;
     }
     return p->data;
 }
 
 //将链表中的元素倒置
 template<typename T>
 void List<T>::reverse()
 {
     if(head == NULL) return;
     Node *pre,*cur,*next;
     pre = head;
     cur = head->next;
     while(cur)
     {
         next = cur->next;
          cur->next = pre;
          pre = cur;
          cur = next;
      }
      head->next = NULL;
      head = pre;
 }
 
 
 template class List<T>; // 显式实例化
 
 链表测试文件 listTest.cpp
 
#include <iostream>
 #include "list.h"
 
 //typedef int T;
 using namespace std;
 
 int main()
 {
     List<T> l;
     List<T> m;
     l.push_front(5); //5
     l.push_front(8); //8 5
     l.push_front(20);// 20 8 5
     l.insert(9,2); // 20 8 9 5
     l.insert(8,100); //6 20 8 9 5
     l.insert(11,-10);//11 6 20 8 9 5
     l.insert(9,2);//11 6 1 20 8 9 5
     l.push_back(10).push_back(19);//11 8 9 20 8 9 5 10 19
     l.travel();
     l.reverse();
     l.travel();
 
     l.remove(8);
     l.remove(9);
     l.set(1,33);
     l.set(l.find(19),-8);
 
 //    cout << l.front() << "      " << l.back() << endl;
     l.travel();  // 11 33 5 10 -8 
 
 //    while(!l.empty()) l.erase(0);
  //   cout << l.size() << endl;
     
  //   cout << l.getElementAtIndex(0) << endl;
     m.insert(-9,0);
     m.insert(13,1);
     m.push_front(-5);
     m.push_back(2);
     cout << "========m链表原始值======" << endl;
     m.travel();// -5 -9 13 2
 
     m = l;
     cout <<"==========将链表m中元素倒置==========" << endl;
     m.reverse();
     m.travel();
     cout <<"===========程序结束======" << endl;
 
     return 0;
 }
 
 
 

一个单向链表中可能存在循环，如何判断单向链表中是否存在循环，又如何找到循环部分的起始节点？如果是非循环链表，如何找到中间节点？
 本文结合网上找到的资料及自己的分析，进行了总结。
 
 
链表节点定义如下：
 
typedef struct _node
 {
 int data;
 struct _node *next;
 }node,*pnode;
 
 
1、判断单向链表中是否存在循环链表
 
思路：设置两个指针，初始值都指向头节点，然后开始遍历，一个指针每次走一步，另一个指针每次走两步，如果存在循环链表，这两个链表肯定能相遇
 
代码：
 
//返回0表示没有循环
 //返回1表示有循环
 int FindLoop(node *head)
 {
 node *pOneStep, *pTwoStep;
 int iReturn = 0;
 if (NULL == head)
 return 0;
 
 
 pOneStep = head;
 pTwoStep = head;
 
 
 while ((NULL!=pTwoStep)&&(NULL!=pTwoStep->next))
 {
 pOneStep = pOneStep->next;
 pTwoStep = pTwoStep->next->next;
 if (pTwoStep == pOneStep)
 return 1;
 }
 return 0;
 }
 
 
2、找到单向非循环链表的中间节点
 
注意，是非循环链表
 
思路：设置两个指针，初始值都指向头节点，然后开始遍历，一个指针每次走一步，另一个指针每次走两步，走两步的指针到链表末尾时，走一步的指针刚好就指向了中间节点
 
 
代码：
 
 node* FindNoLoopListMiddleNode(node *head)

 {

 
node *pOneStep, *pTwoStep;

 
if (NULL == head || NULL==head->next)

 
return head;

 
pOneStep = head;

 
pTwoStep = head;

 

 

 
while ((NULL != pTwoStep) && (NULL != pTwoStep->next))

 
{

 
pTwoStep = pTwoStep->next->next;

 
if (NULL != pTwoStep)

 
pOneStep = pOneStep->next;

 
}

 
return pOneStep;

 } 

 
 
3、查找单向循环链表中的循环部分的起始节点
 
方法一：
 
首先用判断单向链表中是否存在循环链表的思路到达相遇节点，然后设置两个指针，分别从相遇节点和头节点单步进行遍历，两个指针相遇的节点就是循环的起始节点
 
关于这个思路的详细解释请自行查询或参考链接：http://www.cnblogs.com/cyttina/archive/2012/10/28/2743760.html
 
 
//寻找环的入口点
NodeList FindLoopPort(NodeList head)
{
    NodeList slow=head,fast=head;
    //得到相遇点
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
            break;
    }
    if(fast==NULL||fast->next==NULL)
        return NULL;
    //slow指向开头，fast在相遇点
    //得到入口点
    slow=head;
    while(slow!=fast){
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}
 

 
 
方法二：
 
思路： 设置两个指针 p1和p2，用p2遍历整个链表，用p1遍历p2走过的节点，当p1等于p2->next时，p1就是循环部分的起始节点。
 
这种方法与第一种方法相比，理解起来会简单很多，但算法复杂度有所提高。
 
代码：
 
//没有循环返回NULL
 //如果存在循环返回循环起始节点的指针
 node* FindLoopNode(node *head)
 {
 node *pc = head;
 node *pf = NULL;
 if (!pc)
 return NULL;
 while (pc)
 {
 pf = head;
 while(pf && pf != pc)
 {
 //当前结点的下一个结点是它前面的某个结点或者是它自己，则为循环处
 if (pc->next == pf || pc->next == pc)
 return pc->next;
 pf = pf->next;
 }
 pc = pc->next;
 }
 return NULL;
 }

欢迎加qq群：453398542 学习讨论，会定期分享资料课程，解答问题。
 
1、         有10个学生，每个学生的数据包括学号、姓名和1门课成绩，编写如下函数：
 
（1）    根据学生的信息建立链表；
 
（2）    输出链表；
 
（3）    输入一个学生的学号，查找链表中是否有该学生；
 
（4）    在第i个学生前插入一个学生信息；
 
（5）    删除链表中第i个学生。
 
#include<stdio.h>
 
#include<stdlib.h> 
 
#define N 10
 
typedef struct Student{
 
int num;
 
char name[20];
 
float score;
 
}S;
 
typedef struct Node{
 
S date;
 
struct Node *next;
 
}Node,*LinkList;
 
LinkList createlist(int n){
 
int i;
 
LinkList head,pre,p;
 
head=pre=(LinkList)malloc(sizeof(Node));
 
for(i=0;i<n;i++){
 
p=(LinkList)malloc(sizeof(Node));
 
scanf("%d%s%f",&(p->date.num),p->date.name,&(p->date.score));
 
pre->next=p;
 
pre=p;
 
}
 
pre->next=NULL; 
 
return head; 
 
}//输入 
 
void output(LinkList head){
 
LinkList p;
 
p=head->next;
 
while(p!=NULL){
 
printf("%5d%10s%5.1f\n",p->date.num,p->date.name,p->date.score);
 
p=p->next;
 
}
 
printf("\n");
 
}//输出 
 
void search(LinkList head,int n){
 
LinkList p;
 
p=head->next;
 
while(p!=NULL)
 
if(p->date.num==n)
 
break;
 
else
 
p=p->next;
 
if(p==NULL)
 
printf("表中无学号为%d的学生。\n",n);
 
else
 
{
 
printf("满足条件的同学的信息如下：\n");
 
printf("%8d%10s%.1f",p->date.num,p->date.name,p->date.score);
 
}
 
printf("\n");
 
}//查找 
 
LinkList insert_node(LinkList head,int i,S st){
 
int j;
 
LinkList p,s;
 
p=head; j=0;
 
while(p!=NULL&&j<i){
 
j++; p=p->next;
 
}
 
if(!p||j>i){
 
printf("传递的参数非法\n");
 
return NULL;
 
}
 
s=(LinkList)malloc(sizeof(Node));
 
s->date=st;
 
s->next=p->next;
 
p->next=s;
 
return 0;
 
} //插入 
 
LinkList delete_node(LinkList head,int i){
 
int j;
 
LinkList p,q;
 
p=head; j=1;
 
while(p->next!=NULL&&j<i){
 
j++; p=p->next;
 
}
 
if(!p->next||j>i){
 
printf("传递的数据非法\n");
 
return NULL;
 
}
 
q=p->next; p->next=q->next;
 
free(q);
 
return head;
 
}//删除 
 
int main(){
 
int i,n,a,b;
 
S stu;
 
LinkList head;
 
printf("输入学生个数：\n");
 
scanf("%d",&n);
 
  head=createlist(n);
 
  output(head);
 
    printf("输入一个学生的学号：\n");
 
  scanf("%d",&a);
 
  search(head,a);
 
  printf("插入一个学生；\n");
 
  scanf("%d%s%f",&stu.num,stu.name,&stu.score);
 
  printf("输入插入位置：\n");
 
  scanf("%d",&i);
 
  insert_node(head,i,stu);
 
  printf("删除第%d个学生；\n",i);
 
  delete_node(head,i);
 
  output(head);
 
return 0;
 
}