[数据结构与算法]链表算法笔记

?反转一个链表

struct list_node* resverse_list(struct list_node* head){
    struct list_node* current = head;
    struct list_node* prev    = NULL;   
    while(current){
        struct list_node* node = current->next;     指向第二个节点
        current->next = prev;                       第一个节点指向NULL
        prev = current;                             前继节点后移
        current = node;                             当前节点后移
    }   
}

单向链表如何找到倒数n个节点

---->用两个指针 ，第一个先走n步,然后两个指针同时走,当第一个指针走到尾时,返回第二个指针

struct list_node* GetLastNnode(struct list_node* head , int n){
    struct list_node* pfirst = head;
    struct list_node* psecond = head;
    int count;
    for(count = 0 ; count < n ; count++){
        if(pfirst == NULL)
            break;
        pfirst = pfirst->next;
    }
    if( n != count)                     // 长度不够n
        return NULL;
    while(pfirst != NULL){
        psecond = psecond->next;
        pfirst = pfirst->next;
    }
    return psecond;
}

?判断链表是否有环？

----->快慢指针

bool isLoopList(struct list_node* head){
    struct list_node* pfast = head;
    struct list_node* pslow = head;
    while(pfast != NULL && pfast->next != NULL){
        pfast = pfast->next->next;
        pslow = pslow->next;
        if(pfast == pslow)
            return true;
    }
    return false;
}

?判断两个链表是否交叉

struct list_node* FindCrossNode(struct list_node* list1 , struct list_node* list2){
    if(list1 == NULL || list2 == NULL)
        return NULL;
    struct list_node* p1 = list1;
    struct list_node* p2 = list2;
    int len1 = 0;
    int len2 = 0;
    while(p1){
        p1 = p1->next;
        len1++;
    }
    while(p2){
        p2 = p2->next;
        len2++;
    }
    len = len1 > len2 ? len1-len2 : len2-len1;
    struct list_node* long = len1 > len2 ? list1 : list2;
    struct list_node* short = len1 < len2 ? list1 : list2;
    for(int i = 0 ; i < len ; i++){
        long = long->next;
    }
    while(short != NULL && long != NULL && short != long){
        short = short->next;
        long = long->next;
    }
    return short;
}