链表中几个较重要的问题

/*单链表*/
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;
}
}
}

链表倒数m个节点的对象
这种问题的解决方式很多，但是如何保证复杂度上最小却是一个重要的问题，最好是只遍历一次链表就能找到对应的节点，实质上采用类似于哨兵指针的形式就能实现。设置两个指针，分别执行链表头和链表的第m个对象，然后两个指针分别遍历，当执行第m个节点对象的指针指向了最后一个节点对象时，这时指向表头的那个链表实质上就指向了倒数第m个节点的对象。这个指向第m个节点的指针就起到了类似哨兵指针的作用。