单向链表相关

单向链表是微软笔试常考的，参考这里：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;
}