Linked List (4)

Find the middle item in a Linked List

int find_middle(node *head)
{
    node *p1, *p2;
    p1 = p2 = head;
 
    while (p1 != NULL && p1->next != NULL) {
        p1 = p1->next->next; // p1 goes 2 steps; p2 goes 1 step
        p2 = p2->next;// when p1 to the end, p2 points to middle
    }
 
    return p2;
}

Determine if there is a loop in a Linked List
bool find_loop(node *head)
{
    node *p1, *p2;
    p1 = p2 = head;
 
    while (p1 != NULL && p1->next != NULL) {
        p1 = p1->next->next;// p1 goes 2 steps; p2 goes 1 step
        p2 = p2->next;
        if (p1 == p2) // If there is loop, we must get p1 == p2 
            return true;  // sooner or later
    }
 
    return false;     // If goes out of the while, no loop.
}

Find merge point of two Linked Lists (if there is one)
Node* Find_merge_point(Node *h1, Node *h2)
{
    Node *p1, *p2;
 
    int n = Length1(h1) - Length1(h2); 
    if (n >= 0) {  // make p1 to be longer one 
        p1 = h1;
        p2 = h2;
    }
    else {
        n *= -1;
        p1 = h2;
        p2 = h1;
    }
 
    while (n--)// n is the length diff. between p1 and p2
        p1 = p1->next; // make p1 and p2 "aligned" 
 
    while (p1 != p2 && p1 != NULL && p2 != NULL) {
        p1 = p1->next; // start to check merge point
        p2 = p2->next;
    }
 
    if (p1 == NULL || p2 == NULL) {
        printf("can't find merge point!\n");
        return NULL;
    }
    else
        return p1;
}