链表的相关操作---IT应聘中常见

     链表这种常见的基础数据结构，不仅在Linux内核中大量使用，在互联网公司的许多业务中也大量使用。那么，参加IT笔试、面试的，这些方面的知识绝对不会少。各方搜罗打听，整理一下这些常见的操作，以备后用。
    这个是link.h

#ifndef _LINK_H_
#define _LINK_H_

#define TRUE 1
#define FALSE 0

//链表的控制信息
typedef struct Link
{
    struct LinkNode *head; //指向链表的头节点
    int count; //链表中的元素个数
}Link;

//链表节点的结构体
typedef struct LinkNode
{
    int data; //数据域
    struct LinkNode * next; //指针域
}LinkNode;


typedef unsigned char Boolean;

Link *init_link(void) ; //链表的初始化
void     destroy_link(Link **link); //链表的销毁
void     push_front(Link *link, int value); //头部插入
void     push_back(Link *link, int value); //尾部插入
Boolean  pop_front(Link *link); //头部删除
Boolean  pop_back(Link *link); //尾部删除
void     show_link(Link *link); //显示链表的信息
void     sort_link_ascend(Link *link); //升序排列单链表
void     sort_link_descend(Link *link); //降序排列单链表
Link *merger_two_links(Link *link1, Link *link2);
//普通归并两个有序单链表
Link *merger_two_links_recure(Link *link1, Link *link2);
//递归地归并两个有序的单链表
Link *copy_link(Link *link); //单链表的拷贝
int get_link_count(Link *link); //得到链表的节点数目
LinkNode *find_mid_node(Link *link); //找到链表的中间节点
LinkNode *find_reciprocal_node(Link *link, int num); //找到链表的倒数第n个节点
Link *reverse_link(Link *link); //反转链表
void     recur_reverse_print_link(Link *link); //逆序打印链表
Boolean  has_circle(Link *link); //判断链表是否有环
Boolean  is_link_intersect(Link *link1, Link *link2);
//判断两个链表是否有交点
LinkNode *get_first_common_node(Link *link1, Link *link2);
//找到两个相交链表的第一个交点
void delete_one_node(Link *link, LinkNode *node);
//在O（1）时间复杂度删除链表节点
LinkNode *get_first_node_in_circle(Link *link);
//得到环内的第一个节点

#endif

#include "link.h"

Link *init_link(void) //链表初始化
{
    Link *link = (Link *)malloc(sizeof(Link));
    if(link == NULL){
        fprintf(stderr, "the memory is full!\n");
        exit(1);
    }
    bzero(link, sizeof(Link));
    link->head = buy_node(); //为链表购买头节点
    return link;
}

void     destroy_link(Link **link) //链表的销毁
{
    LinkNode *p_node = NULL;

    if(link == NULL || (*link) == NULL){ //如果链表不存在，直接退出
        return ;
    }

    p_node = (*link)->head;
    while(p_node != NULL){ //循环地删除链表的节点
        (*link)->head = (*link)->head->next;
        free(p_node);
        p_node = (*link)->head;
    }
    free(*link); //删除链表的控制信息节点
    *link = NULL; //为了安全起见，将链表的控制信息指针指向NULL
}

void     push_back(Link *link, int value) //尾部插入
{
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;

    if(link == NULL || link->head == NULL){ //判断链表的控制信息和链表是否存在
        return ;
    }

    p_node = link->head; //指向链表的点
    while(p_node->next != NULL){ //找到最后一个节点
        p_node = p_node->next;
    }
    // 找到最后一个节点的位置，购买一个新的节点，
    // 赋予设定值，并且添加到链表的末尾
    q_node = buy_node();
    q_node->data = value ;
    p_node->next = q_node ;
    (link->length)++ ; //链表长度增加1
}

void     push_front(Link *link, int value) //头部插入
{
    LinkNode *p_node = NULL;

    if(link == NULL || link->head == NULL){ //判断链表的控制信息和链表是否存在
        return ;
    }

    p_node = buy_node() ; //购买新的节点并赋初值
    p_node->data = value ;
    p_node->next = link->head->next;
    link->head->next = p_node ; //将新生成的节点添加到链表的第一个节点
    (link->length)++ ;
}

Boolean  pop_back(Link *link) //尾部删除结点
{
    Boolean ok = FALSE;
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;

    if(link == NULL || link->length == ZERO){ //如果链表不存在或者没有节点，返回尾部删除失败
        return ok;
    }
    if(link->length == ONLY_ONE){ //如果只有一个链表节点，直接删除
        free(link->head->next);
        link->head->next = NULL;
    }else{ //找到最后一个节点
        for(p_node = link->head->next; p_node->next != NULL;
            p_node = p_node->next){
            q_node = p_node; //记录下最后一个节点的上一个节点位置
        }
        free(p_node);
        q_node->next = NULL;
    }
    (link->length)--;
    return ok = TRUE;
}

Boolean  pop_front(Link *link) //头部删除结点
{
    Boolean ok = FALSE;
    LinkNode *p_node = NULL;

    if(link == NULL || link->length == ZERO){ //如果链表不存在直接返回删除失败
        return ok;
    }
    p_node = link->head->next;
    link->head->next = p_node->next;
    free(p_node);
    (link->length)--;
    return ok = TRUE;
}

static void swap_link_node(LinkNode *node1, LinkNode *node2) //交换两个链表的节点信息
{
    LinkNode temp = *node1;
    *node1 = *node2;
    *node2 = temp;
}

//交换两个链表节点的next值
static void swap_link_pointer(LinkNode **pointer1, LinkNode **pointer2)
{
    LinkNode *temp = *pointer1;
    *pointer1 = *pointer2;
    *pointer2 = temp;
}

void     sort_link_ascend(Link *link) //单链表的升序排列
{
    LinkNode *p_node = NULL; //冒泡排序中的i
    LinkNode *q_node = NULL; //冒泡排序中的j
    LinkNode temp = {0}; //链表节点的中间变量
    LinkNode *p_temp = NULL; //链表节点指针的中间变量

    //当链表不存在或者只有一个节点时，不需要进行排序
    if(link == NULL || link->head == NULL || link->length == ONLY_ONE){
        return ;
    }

    for(p_node = link->head->next; p_node != NULL; p_node = p_node->next){
        for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
            //模仿冒泡排序进行
            if(p_node->data > q_node->data){
                swap_link_node(p_node, q_node); //交换两个链表的节点信息
                swap_link_pointer(&(p_node->next), &(q_node->next)); //交换两个链表节点的next值
            }
        }
    }
}

void     sort_link_descend(Link *link) //单链表的降序排列
{
    LinkNode *p_node = NULL; //冒泡排序中的i
    LinkNode *q_node = NULL; //冒泡排序中的j
    LinkNode temp = {0}; //链表节点的中间变量
    LinkNode *p_temp = NULL; //链表节点指针的中间变量

    //当链表不存在或者只有一个节点时，不需要进行排序
    if(link == NULL || link->head == NULL || link->length == ONLY_ONE){
        return ;
    }

    for(p_node = link->head->next; p_node != NULL; p_node = p_node->next){
        for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
            //模仿冒泡排序进行
            if(p_node->data < q_node->data){
                swap_link_node(p_node, q_node); //交换两个链表的节点信息
                swap_link_pointer(&(p_node->next), &(q_node->next)); //交换两个链表节点的next值
            }
        }
    }
}

void     show_link(Link *link) //显示链表信息
{
    LinkNode *p_node = NULL;

    if(link == NULL || link->head == NULL){ //判断链表控制信息和链表头节点是否存在
        return ;
    }
    printf("show link messages:\n");
    for(p_node = link->head->next; p_node != NULL;
        p_node = p_node->next){ //从头到尾依次遍历每个链表节点
        printf("%d   ", p_node->data);
    }
    printf("\n");
}

Link *merger_two_links_recure(Link *link1, Link *link2) //递归的合并两个链表
{
    Link *result = NULL;
    if(link1 == NULL || link2 == NULL
     || (link1->length == ZERO && link2->length == ZERO)){
        return result;
    }


    result = init_link(); //初始化链表
    result->head->next = merger_links(link1->head->next, link2->head->next);
    result->length = link1->length + link2->length;
    return result;
}

static LinkNode *merger_links(LinkNode *link1_first, LinkNode *link2_first) //进行链表的递归合并
{
    LinkNode *result = NULL;

    if(link1_first == NULL){ //本链表为空，返回另外一个链表
        return copy_link_by_node(result, link2_first);
    }else if(link2_first == NULL){
        return copy_link_by_node(result, link1_first);
    }

    if(link1_first->data < link2_first->data){
        result = buy_node();
        result->data = link1_first->data;
        result->next = merger_links(link1_first->next, link2_first);
    }else{
        result = buy_node();
        result->data = link2_first->data;
        result->next = merger_links(link1_first, link2_first->next);
    }
    return result;
}

static LinkNode *copy_link_by_node(LinkNode *des_link, LinkNode *src_link) //通过节点来拷贝链表
{
    LinkNode *result = NULL;
    LinkNode *p_node = NULL;

    if(src_link == NULL){ //如果源链表不存在直接返回
        return NULL;
    }

    //否则进行拷贝
    des_link = buy_node();
    result = p_node = des_link ;
    des_link->data = src_link->data;
    src_link = src_link->next;
    while(src_link != NULL){
        des_link = buy_node() ;
        des_link->data = src_link->data;
        p_node->next = des_link ;
        p_node = des_link ;
        src_link = src_link->next;
    }

    return result;
}

Link *copy_link(Link *src_link) //通过控制信息来拷贝链表
{
    Link *des_link = NULL;
    LinkNode *p_node = NULL;

    if(src_link == NULL){ //源链表不存在，无需进行拷贝
        return NULL;
    }

    des_link = init_link(); //初始化链表
    p_node = src_link->head->next;

    while(p_node != NULL){
        push_back(des_link, p_node->data);
        p_node = p_node->next;
    }

    return des_link;
}

Link *merger_two_links(Link *link1, Link *link2) //合并两个有序链表
{
    Link *result = NULL;
    LinkNode *link1_move = NULL;
    LinkNode *link2_move = NULL;

    //如果两个链表不存在或者没有元素的话，则不进行合并
    if(link1 == NULL || link2 == NULL ||
        link1->length == ZERO || link2->length == ZERO){
            return NULL;
    }

    //对链表进行排序
    sort_link_ascend(link1);
    sort_link_ascend(link2);

    //show_link(link1);
    //show_link(link2);

    result = init_link(); //初始化结果链表
    //合并两个链表
    //
    //1.首先让各个链表都指向初始化位置
    link1_move = link1->head->next;
    link2_move = link2->head->next;

    while(link1_move != NULL && link2_move != NULL){
        //如果link1链表当前节点的元素值大与link2，则把link1的节点元素值尾插到result末尾
        if(link1_move->data < link2_move->data){
            push_back(result, link1_move->data);
            link1_move = link1_move->next;
        }else{
            push_back(result, link2_move->data);
            link2_move = link2_move->next;
        }
    }

    //当两个链表中有任意一个遍历完毕，把另外一个链表追加到result末尾
    if(link1_move == NULL){
        while(link2_move != NULL){
            push_back(result, link2_move->data);
            link2_move = link2_move->next ;
        }
    }
    if(link2_move == NULL){
        while(link1_move != NULL){
            push_back(result, link1_move->data);
            link1_move = link1_move->next ;
        }
    }
    return result;
}

static LinkNode *buy_node(void) //购买链表结点
{
    LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
    if(node == NULL){
        fprintf(stderr, "the memory is full!\n");
        exit(1);
    }
    bzero(node, sizeof(LinkNode));
    return node;
}

int get_link_length1(Link *link) //求链表长度
{
    int count = 0;
    LinkNode *p_node = NULL;

    if(link == NULL || link->head == NULL){ //如果链表不存在，直接返回负值
        return -1;
    }

    p_node = link->head->next; //让p_node指向链表的第一个节点
    while(p_node != NULL){
        count++;
        p_node = p_node->next;
    }

    return count;
}

int get_link_length2(Link *link) //求链表长度
{
    if(link == NULL){
        return -1;
    }
    return link->length;
}

Link *reverse_link_nonrecure(Link *link) //翻转链表
{
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;
    LinkNode *head = NULL;

    //如果链表不存在或者链表元素为0或者链表元素为1，则不进行反转
    if(link == NULL || link->length == ZERO
     ||link->length == ONLY_ONE){
        return link;
    }

    p_node = head = link->head->next; //指向第一个节点
    head = head->next ; //指向第二个节点
    q_node = head->next ; //指向第三个节点

    if(q_node == NULL){ //如果只有两个节点
        head->next = p_node;
        p_node->next = NULL;
    }else{ //如果是三个或三个以上节点
        p_node->next = NULL ;
        do{
            head->next = p_node ;
            p_node = head ;
            head = q_node ;
            q_node = q_node->next;
        }while(q_node != NULL);
        head->next = p_node ;
    }

    link->head->next = head;
    return link;
}

LinkNode *find_reciprocal_node1(Link *link, int num) //查找链表的倒数第k个节点（简便）
{
    int move_count = 0 ;
    LinkNode *p_node = NULL;
    //如果链表不存在或者是空链表,或者倒数的数字大于链表的长度，则直接返回NULL
    if(link == NULL || link->length == ZERO
    || num > (link->length) || num <= 0){
        return NULL;
    }
    move_count = link->length - num; //总数-倒数的个数==移动的节点数
    p_node = link->head->next ;

    while(move_count > 0){
        p_node = p_node->next;
        move_count--;
    }

    return p_node;
}

LinkNode *find_reciprocal_node2(Link *link, int num) //查找链表的倒数第k个节点
{
    LinkNode *prev_node = NULL;
    LinkNode *next_node = NULL;
    int i = 0;

    if(link == NULL || link->length == ZERO || num <= 0){
        return NULL;
    }

    //先遍历和后遍历的指针都指向初始位置
    prev_node = link->head->next;
    next_node = link->head->next;

    for(i = 0; i < num - 1; ++i){
        if(prev_node->next != NULL){
            printf("prev:%d %ld\n", prev_node->data, prev_node);
            prev_node = prev_node->next;
        }else{
            return NULL;
        }
    }

    //让先前的节点先走k步，再让后续节点从头遍历，当先前的
    //节点到达末尾时，后续的节点就是指向了倒数第k个
    while(prev_node->next == NULL){
        prev_node = prev_node->next;
        next_node = next_node->next;
    }

    printf("next:%d  %ld\n", next_node->data, next_node);
    return next_node;
}

LinkNode *find_mid_node1(Link *link) //查找链表中间结点
{
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;

    if(link == NULL || link == ZERO){
        return NULL;
    }

    p_node = link->head->next;
    q_node = link->head->next;

    while(p_node->next != NULL){
        p_node = p_node->next;
        q_node = q_node->next;
        if(p_node->next != NULL){
            p_node = p_node->next;
        }
    }

    return q_node;
}

LinkNode *find_mid_node2(Link *link) //查找链表中间节点
{
    LinkNode *p_node = NULL;
    int move_count = 0 ;

    if(link == NULL || link == ZERO){
        return NULL;
    }

    if(link->length == ONLY_ONE){ //如果只有一个节点，则返回该节点
        return link->head->next;
    }

    move_count = (link->length) / 2 - 1; //找到中间节点需要移动的步数
    p_node = link->head->next;
    while(move_count >= 0){
       p_node = p_node->next;
       move_count--;
    }
    return p_node;
}

void     recur_reverse_print_link(Link *link) //递归逆序打印链表
{
    if(link == NULL || link->length == ZERO){ //如果链表不存在或者没有元素，不进行打印
        return ;
    }
    printf("reverse link message:\n");
    rever_print_link(link->head->next);
    printf("\n");
}

static void rever_print_link(LinkNode *link_first) //递归进行打印
{
    if(link_first == NULL){
        return ;
    }else{
        rever_print_link(link_first->next);
        printf("%d   ", link_first->data);
    }
}

void     nonrecur_reverse_print_link(Link *head) //非递归逆序打印链表
{
    /*使用栈来存储链表的元素，再反向打印*/
}

Boolean  has_circle(Link *link) //判断链表是否有环
{
    Boolean ok = FALSE;
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;

    if(link == NULL || link->length < 2){ //如果链表不存在或者少于两个节点，则不存在环
        return ok;
    }

    p_node = link->head->next;
    q_node = link->head->next;

    while((p_node != NULL) && (p_node->next != NULL)){ //快速移动的指针和它下一个节点都不为空
         p_node = p_node->next->next;
         q_node = q_node->next;

         //如果快速节点和较慢节点相遇，说明它们是在环中相遇的
         if(p_node == q_node){
             return ok = TRUE;
         }
    }

    return ok;
}

Boolean  is_link_intersect(Link *link1, Link *link2) //判断两个链表是否有交点
{
/*
 * 如果两个链表有交点，那么他们的最后一个节点一定相同。
 *
 * */
    Boolean ok = FALSE;
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;

    if(link1 == NULL || link2 == NULL
    || link1->length == ZERO || link2->length == ZERO){
    //如果两个链表不存在，或者说没有元素的话，直接返回无交点
        return ok;
    }

    p_node = link1->head->next;
    q_node = link2->head->next;

    //两个指针各自移动到所属链表的末尾
    while(p_node->next != NULL){
        p_node = p_node->next;
    }

    while(q_node->next != NULL){
        q_node = q_node->next;
    }

    if(p_node == q_node){ //判断末尾指针是否相等
        ok = TRUE;
    }

    return ok;
}

LinkNode *get_fisrt_common_node(Link *link1, Link *link2) //找到链表的第一个交点
{
    int l1_len = 0;
    int l2_len = 0;
    int dis_len = 0;
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;
    //首先判断链表是否有交点，如果没有直接返回NULL
    if(!is_link_intersect(link1, link2)){
        return NULL;
    }

    p_node = link1->head->next;
    q_node = link2->head->next;

    //判断两个链表的长度和差值
    l1_len = link1->length;
    l2_len = link2->length;

    if(l1_len > l2_len){ //如果link1长，则先让它移动l1_len-l2_len步
        dis_len = l1_len - l2_len;
        while(dis_len--){
            p_node = p_node->next;
        }
    }else{
        dis_len = l2_len - l1_len;
        while(dis_len--){
            q_node = q_node->next;
        }
    }

    while(p_node != q_node){ //如果两个指针相等，该节点为交点
        p_node = p_node->next;
        q_node = q_node->next;
    }

    return p_node;
}

LinkNode *get_first_node_in_circle(Link *link) //找到有环单链表中的第一个节点
{
    //先判断是否有环，有的话记录下相交的节点
    LinkNode *p_node = NULL;
    LinkNode *q_node = NULL;
    LinkNode *p_tail = NULL;

    if(link == NULL || link->length < 2){
        return NULL;
    }

    p_node = link->head->next;
    q_node = link->head->next;

    while((p_node != NULL) && (p_node->next != NULL)){
        p_node = p_node->next->next;
        q_node = q_node->next;
        if(p_node == q_node){
            break ;
        }
    }

    if(p_node == NULL || p_node->next == NULL){
        return NULL;
    }

    // 将环中的此节点作为假设的相交的尾节点，将问题转化成求两个链表
    // 相交的第一个节点的问题。
    p_tail = q_node; //记录此节点为末尾节点
    LinkNode *p_head1 = link->head->next;
    LinkNode *p_head2 = p_tail->next;

    //分别记录两个链表到p_tail的长度
    int len1 = 1;
    p_node = p_head1;
    while(p_node != p_tail){
        p_node = p_node->next;
        len1++;
    }

    int len2 = 1;
    q_node = p_head2;
    while(q_node != p_tail){
        q_node = q_node->next;
        len2++;
    }

    p_node = p_head1;
    q_node = p_head2;

    if(len1 > len2){
        int dis = len1 - len2;
        while(dis--){
            p_node = p_node->next;
        }
    }else{
        int dis = len2 - len1;
        while(dis--){
            q_node = q_node->next;
        }
    }

    while(p_node != q_node){
        p_node = p_node->next;
        q_node = q_node->next;
    }

    return p_node;
}

void     delete_one_node(Link *link, LinkNode *be_deleted) //O（1）时间复杂度删除链表节点
{
     LinkNode *temp = NULL;
     //如果链表不存在或者被删除的节点不存在,直接退出
     if(link == NULL || be_deleted == NULL || link->length == ZERO){
         return ;
     }

     if(be_deleted->next != NULL){ //如果被删除节点不是末尾节点
         //先将下一个结点的数据进行复制，然后删除下一个节点
         be_deleted->data = be_deleted->next->data;
         temp = be_deleted->next;
         be_deleted->next = temp->next;
         free(temp);
     }else{ //如果是末尾节点
         pop_back(link);
     }
}

void     show_link_length(Link *link) //显示链表的长度
{
    if(link == NULL){ //如果链表不存在直接退出
        return ;
    }
    printf("the link length is:%d\n", link->length);
}