九个数据结构例子

1.判断链表是否存在环型链表问题:

判断一个链表是否存在环,例如下面这个链表就存在一个环:N1->N2->N3->N4->N5->N2就是一个有环的链表,环的开始结点是N5,这里有一个比较简单的解法。

设置两个指针p1,p2。每次循环p1向前走一步,p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link {     
                   int data;     link* next; 
};
 
bool IsLoop(link* head) {    
 
                   link* p1=head, *p2 = head;     
                   if (head ==NULL || head->next ==NULL)      {      return false;      }    
                   do{         p1= p1->next;         p2 = p2->next->next;     
                   } while(p2 && p2->next && p1!=p2);          
                   if(p1 == p2)    return true;      
                   else           return false; 
}

2,链表反转 单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中当前指针指向的下一个元素,然后将当前节点元素的指针反转后,利用已经存储的指针往后面继续遍历。源代码如下:

struct linka {
                          int data;      linka* next; 
};
void reverse(linka*& head) {     
                          if(head ==NULL)           return;      
                          linka*pre, *cur, *ne;      pre=head;      
                          cur=head->next;      
                          while(cur)      {          
                                                             ne = cur->next;           cur->next = pre;          
                                                             pre = cur;           cur = ne;      
                         }     
                         head->next = NULL;      
                         head = pre;
}
4 days ago, this page was being read.


Subscribe to Comments