文章仍是关于链表，本次首要触及几个比较深化的问题：循环链表的断定、倒数第m个节点的数据获取、多层次链表的规划、平铺和撤销平铺。
/*单链表*/
typedef struct list
{
struct list *next;
int data;
} List_t, *List_handle_t;
/*双向链表*/
typedef struct Dblist
{
struct Dblist *next;
struct Dblist *prev;
int data;
}DList_t, *DList_handle_t;
/*多层次链表*/
typedef struct mullevel_list
{
struct mullevel_list *prev;
struct mullevel_list *next;
struct mullevel_list *child;
intdata;
}MList_t, *MList_handle_t;
关于链表首要仍是搞清楚指针的相关问题。链表头的更新操作也是指针操作的一部分，怎么完结链表头的自动更新也是需求留意的，假如每次都选用返回值的方法完结链表的头的更新，这在实践的操作中十分的不放便，选用指向指针的指针完结链表头的更新将是十分不错的挑选。其实这也是内存分配中常常运用的技巧。
/*内存分配*/
bool GetMemory(char ** str, int n)
{
*str = (char *) malloc(n);
if(*str)
return true;
return false;
}
/*链表头的更新*/
bool insert_listnode(List_handle_t *head, int a)
{
List_handle_t newlistnode = (List_handle_t)malloc(sizeof(List_t)/sizeof(char));
if(*head == NULL && newlistnode != NULL)
{
*head = newlistnode;
newlistnode->data = a;
newlistnode->next = NULL;
return true;
}
else if(*head != NULL ** newlistnode != NULL)
{
newlistnode->data= a;
newlistnode->next = *head;
*head = newlistnode;
return true;
}
return false;
}
其间这种选用指向指针的指针的方法就能够确保链表的自动更新，这种特性首要是C/C++中函数值传递的特性，形参不改动实参的值，可是当传递的是指针时，这时指针实质上便是地址，作为参数时，地址并不会改动，可是地址中的内容是可改动的，这是内存分配问题中常常运用的技巧，如上面的代码所示。这种代码的方法还有一些长处，能够判别判别问题是否完结，经过判别是否需求再次分配。
单链表的逆序问题：
逆序问题实质上首要是完结每一个链表节点的操作，然后更新链表头，这时需求三个指针，其间一个表明逆序链表的表头，一个表明需求操作的节点，最终一个表明下一个行将操作的节点，也便是逆序操作需求保存三个节点才干确保一个逆序的完结。首要确保下一个行将操作的节点存在，然后完结逆序链表表头与实践操作的节点进行指向操作，更新表头。
bool reversed_list(List_handle_t *head)
{
List_handle_t mid ;
List_handle_t fir ;
List_handle_t last;
if(*head != NULL)
{
mid = last =head;
/*save the node next to be operated*/
fir =mid->next;
/*tail of the list*/
last->next = NULL;
while(fir != NULL)
{
/*get the node to be operated*/
mid = fir;
/*save the node next to be operated*/
fir = fir->next;
/*link to the head of list*/
mid->next = last;
/*update the head of list*/
last =mid;
}
/*return the actual list head*/
*head= last;
return true;
}
return false;
}
关于链表是否为循环链表的问题，这种问题是一个经典的问题，由于链表操作实质上便是指针的比较高档的操作。所以一般都需求依仗指针进行操作。怎么判别是否为循环呢？假如是像数组那种接连的内存空间能够经过指针的值进行判别，接连性就能使得指针的比较存在含义，可是链表是一个非接连的内存空间，对指针进行比较就没有任何的含义。一般选用快慢指针的方法进行判别。
两个指针，其间一个指针以每次一个目标的方法遍历链表，另一个链表以每次多个目标的方法遍历，假如对错循环的链表，那么快的指针会首要抵达链表的尾部。可是假如是循环链表，这时快指针的遍历速度快，由于存在循环，就会存在快指针指向慢指针后边目标的时间，假如快指针指向的目标便是慢指针指向的目标或许快指针的下一个目标便是慢指针指向的目标（这两种状况都适宜，这需求一句循环链表中的目标进行确认），就说明晰链表是一个循环链表。快指针的拜访速度能够设置为每次两个目标，这样就能完结判别。如下所示：
bool isTermination(List_handle_t list)
{
List_handle_t slow , fast;
slow = fast = list;
while(1)
{
if(!fast || !fast->next)
return false;
else
{
/*快指针以2倍速度循环*/
fast = fast->next->next;
/*慢指针以1倍速度循环*/
slow = slow->next;
if(fast == slow || fast->next== slow)
return false;
}
}
}
