合并单向循环链表

合并单向循环链表

题目

已知非空链表（a1,a2,a3,a4,a5,…,an）仅采用设置尾指针的单向链表作为存储结构（设尾指针为rear），请写一算法，将线性表改造为（a1,a2,a3,a4,…,an-1,an,an-1,…,a4,a3,a2,a1）.
要求：改造后的线性表次奥用仅设置尾指针rear的单向链表，并且算法中只有一个循环列表。

分析

思路，结果是关于an对称的线性表。
第一步：设指针q从rear->link开始依次遍历链表，
第二步：并且记录链表的第一个结点，假如由指针r指向。
第三步：拷贝q所指的结点信息，假设有p所指。
第四步： 将p插入到尾指针rear所指的后面。
第五步：循环第三步，第四步。
第六步：将rear指向r所指的位置，形成循环。

示例

初始时：（a1,a2,a3,a4,a5,…,an）
改变后：（a1,a2,a3,a4,…,an-1,an,an-1,…,a4,a3,a2,a1）

代码

// 合并单向循环链表
LinkList MERGELIST(LinkList rear){    
	LinkList p,q,r,s;    
	q=rear->link;    
	p=(LinkList)malloc(sizeof(BNode));    
	p->data = q->data;  // 复制q所指的数据信息    
	r=p;  // 记录第一个元素的位置    
	p->link=rear->link; // 将第一个元素插入链表末尾    
	rear->link=p;    
	q=q->link;     // 指向第二个元素    
	while (q!=rear)    {        
		s = q->link;   // q所指的指针下移        
		p=(LinkList)malloc(sizeof(BNode));  // 申请空间        			         p->data=q->data;   // 复制q所指的数据信息        
		p->link=rear->link;  // 将p插入rear所指的后面        	  		         rear->link=p;        
		q=s;            // 获得下一个处理的结点   
	 }
         rear=r; // 将尾指针指向r的位置，尾指针。   
          return rear;    
  }