单链表

1.如何判断链表是否有环？

基本思想：设定两个变量fast, slow，变量的初始值都是head节点，fast变量每次走两步(fast->next->next), slow变量每次走一步(slow->next), 如果fast 跟slow相遇，那么说明链表肯定有环。

bool isExistLoop(slist *head){

      slist *fast=head, *slow=head;

     

      while(fast && fast->next){

        fast=fast->next->next;

        slow=slow->next;

        if(fast==slow) break;}

      return (fast!=NULL && fast->next!=NULL);

}

 

 

2.已知单链表的head节点，进行单链表逆置。

基本思想：设定3个节点，p1, p2, p3; p1 = head; p1->next=NULL; 每次都把p2的下一个节点指向p1, 然后将p1, p2, p3都向后移一位，循环进行p2的下一个节点指向p1的操作，一直到p3的下一个节点等于NULL时跳出循环。然后再进行一次p2的下一个节点指向p1的操作，最后将p2的值赋给head节点，完成单链表逆置。

 

Node * ReverseList(Node *head) //链表逆序

　　{

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

　　return head;

　　Node *p1 = head ;

　　Node *p2 = p1->next ;

　　Node *p3 = p2->next ;

　　p1->next = NULL ;

　　while ( p3 != NULL )

　　{

　　p2->next = p1 ;

　　p1 = p2 ;

　　p2 = p3 ;

　　p3 = p3->next ;

　　}

　　p2->next = p1 ;  //这步非常重要，千万别忘了！

　　head = p2 ;

　　return head ;

　　}