链表中几个较重要的问题

List_handle_t findMlastnode(List_handle_t list, int m)
{
int n = 0;
List_handle_t temp = list;
List_handle_t mtemp = NULL;

if(temp != NULL)
{
/*find the mth node*/
while( temp != NULL && n != m)
{
temp = temp->next;
++ n;
}

if(n == m && temp != NULL)
{
/*point to the mth node*/
mtemp = temp;
/*point to thehead*/
temp = list;

/*pass the list*/
while(mtemp->next != NULL)
{
mtemp = mtemp->next;
temp = temp->next;
}

return temp;
}
}
return NULL;
}

关于多层次链表的平铺操作，因为多层次链表是类似于树的结构，当然可以采用类似树的遍历形式进行平铺，但是这种方式对节点的访问形式往往都是多次遍历。由于多层次的链表平铺还需要取消平铺操作，因此最好不要破坏每一个层次中的链接关系，如果破坏了每一层中的链接关系，就会使得每一层的还原操作非常复杂，我们可以按照层次逐层逐层的访问。

多层次链表的平铺最好的方式是充分利用尾节点，也就是将每一层的对象都接到平铺链表的尾部，而且随着平铺链表长度的增长，下一层次的节点也能够访问到，这时候通过判断节点是否存在子层，如果有就继续添加到尾节点，这样就能实现不同层次节点的平铺。这种平铺操作的优点在于只遍历了一次第一层的节点完成平铺操作，而且没有破坏每一层对象的链接关系，便于后期的还原。这种方法的关键在于如何控制链表的尾节点。

/*addsublevel listnode to the tail of first level*/
void appendtail(MList_handle_thead, MList_handle_t *tail)
{
MList_handle_t list = head;

/*update the list tail*/
(*tail)->next = head;
head->next= (*tail);

/*pass the node in this list*/
for(list; list->next != NULL; list= list->next);

/*updatathe list tail*/
*tail = list;
}

void flattenList(MList_handle_t head, MList_handle_t *tail)
{
MList_handle_t list =head;

/*list will be growing*/
while(list)
{
if(list->child)
{
appendtail(list->child,tail);
}

list = list->next;
}
}

取消平铺操作，主要是切断每一层之间的前后链接关系，而保持子层链接关系，实质上这可以采用递归的形式实现，因为如果当前节点存在子节点，那么就将子节点的链接关系切断，如果子节点也仍然存在子节点，那么先切断子层的链接关系，因为平铺没有破坏每一层的链接关系，这样只访问第一层就能完成取消平铺操作。实质完成的操作就是讲当前子节点的前一个节点的后一个节点设置为NULL，而将当前子节点的前一个对象设置为NULL，这样就切断了各层之间的关系。因为每一次切断都会导致平铺链表的缩短，当平铺链表只有原始第一层的长度时，这时候就完成了链表的取消平铺操作，当然仍然需要注意尾节点的管理问题。但是我们不能将取消平铺操作直接设置成一个递归操作，平铺操作最后肯定会管理链表尾，而子层与母层的链表断裂关系并不需要设置链表尾。

void unflattensearch(MList_handle_t head)
{
MList_handle_t list =head;

while(list)
{
if(list->child)
{
/*break the link between two levels*/
list->child->prev->next = NULL;
list->child->prev = NULL;

/*break the link between other levels*/
unflattensearch(list->child);
}
/*next listnode*/
list = list->next;
}
}

/*************************************************************
this function can not be reserve
because the function must update tail
actual there is only one time to operate.
**************************************************************/
void unflattenList(MList_handle_t head, MList_handle_t * tail)
{
MList_handle_t list =head;

unflattensearch(list);

/*pass to the last of list*/
for(list; list->next; list = list->next);

/*update the tail of list*/
*tail = list;
}

总结

关于链表的操作我认为主要还是要设置恰当的指针，链表的操作就是指针的操作，但是因为链表的特殊性，使得指针的比较操作变得无效，但是可以通过指针的相等和不相等进行操作，设置哨兵指针等指针的重要操作。

同时需要注意链表是一个可能动态增长的对象，只要时刻理解这种动态特性就能比较好的理解链表中的多层次问题，平铺过程就是利用了链表的动态增长过程，通过链表尾实现动态操作。而取消平铺操作只是完成了切断各层之间的连接关系而已，并不会更新链表尾，但是链表的长度也发生了动态变化。

把握链表的动态增长特性和指针的相关操作就能很好的完成链表的相关操作。