链表中几个较重要的问题

文章还是关于链表，本次主要涉及几个比较深入的问题：循环链表的判定、倒数第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;

    int data;
}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个节点的指针就起到了类似哨兵指针的作用。

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 the head*/
            temp = list;

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

            return temp;
        }
    }
    return NULL;
}

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

 

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

/*add sublevel listnode to the tail of first level*/
void appendtail(MList_handle_t head, 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);

    /*updata the 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;
}

 

总结

 

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

 

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

 

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