链表算法

定位链表中间节点

Node *getMiddleNode(Node * head){
    
    if(head == NULL){
        return NULL;
    }

    Node *p1 = head;
    Node *p2 = head;

    while(p2 != NULL && p2->next != NULL){
        p1 = p1->next;
        p2 = p2->next->next;
    }
    return p1;
}

链表反转

Node *reverseNode(Node * head){
    
    if(head == NULL || head->next == NULL){
        return NULL;
    }

    Node *next = NULL;
    Node *pre = NULL;

    while(head != NULL){
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

链表是否有环, 返回的是环的位置，0代表没有环

int checkLoopNode(Node * head){
    
    if(head == NULL || head->next == NULL){
        return 0;
    }

    Node *p1 = head;
    Node *p2 = head;
    int loc = 0;

    while(1){
        if(p1->next == NULL){
            return 0;
        }
    
        if(p1->next->next != NULL) {
            p1 = p1->next->next;
            p2 = p2->next;
            loc++;
        } else {
            p1 = p1->next;
        }
        
        if(p1 == p2){
        
            // 去除环
            // p2->next = NULL;
            return loc;
        }
    }
    return 0;
}