面試中常考的單鏈表處理

[cpp]
#include<stdio.h>  
#include<stdlib.h>  
#include<assert.h>  
 
struct node 
{ 
    int data; 
    struct node *next; 
}linknode; 
 
typedef struct node * LinkNode; 
LinkNode head = NULL; 
 
LinkNode createNode(int data) 
{ 
    LinkNode node = NULL; 
    node = (LinkNode)malloc(sizeof(linknode)); 
    node->data = data; 
    node->next = NULL; 
    return node; 
} 
//在insert函數中返回head後head的值就不會為空,而不返回head時就返回空  
LinkNode insert(LinkNode head, int data) 
{ 
    if(head == NULL) 
    { 
        head = createNode(data); 
        return head; 
    } 
    LinkNode node = NULL; 
    node = createNode(data); 
    node->data = data; 
    node->next = head->next; 
    head->next = node; 
    return head; 
} 
 
void traverse(LinkNode head) 
{ 
    LinkNode p = NULL; 
    p = head; 
    while( NULL != p) 
    { 
        printf("%d ", p->data); 
        p = p->next; 
    } 
} 
 
void linkListFree(LinkNode head) 
{ 
    assert(head != NULL); 
    LinkNode p = head; 
    LinkNode q; 
    while( NULL != p) 
    { 
        q = p->next; 
        free(p); 
        p = NULL; 
        p = q; 
    } 
} 
 
LinkNode reverse(LinkNode head) 
{ 
    assert(head != NULL); 
    LinkNode ptr = createNode(-1); 
    ptr->next = head; 
    LinkNode p = head->next; 
    head->next = NULL;//必須對head->next置空,不然出現循環  
    LinkNode q = NULL; 
    while(p != NULL) 
    { 
        q = p->next; 
        p->next = ptr->next; 
        ptr->next = p; 
        p = q; 
    } 
    return ptr->next; 
} 
 
//無頭單鏈表刪除節點  
void deleteRandomNode(LinkNode p) 
{ 
    assert(p != NULL); 
    LinkNode n = p->next; 
    if(n != NULL) 
    { 
        p->data = n->data; 
        p->next = n->next; 
        free(n); 
        n = NULL; 
    } 
} 
 
//判斷兩個鏈表是否相交  
bool isIntersect(LinkNode headone, LinkNode headtwo) 
{ 
    assert( (headone!=NULL) && (headtwo!=NULL) ); 
    LinkNode p = headone; 
    while(p->next != NULL) 
    { 
        p = p->next; 
    } 
    LinkNode q = headtwo; 
    while( (NULL != q) && (q != p) ) 
    { 
        q = q->next; 
    } 
    if(q == NULL) 
        return false; 
    return true; 
} 
 
 
//如果相交找到相交的第一個節點  
LinkNode firstIntersectNode(LinkNode headone, LinkNode headtwo) 
{ 
    assert( (NULL != headone) && (NULL != headtwo) ); 
    int lenone = 0, lentwo = 0; 
    LinkNode p = headone; 
    while(NULL != p) 
    { 
        lenone++; 
        p = p->next; 
    } 
    p = headtwo; 
    while(NULL != p) 
    { 
        lentwo++; 
        p = p->next; 
    } 
    if(lenone < lentwo) 
    { 
        p = headtwo; 
        for(int i=0; i<(lentwo-lenone); i++) 
        { 
            p = p->next; 
        } 
        LinkNode q = headone; 
        while( (NULL != p) && (NULL != q) ) 
        { 
            if(p == q) 
                return p; 
            else 
            { 
                p = p->next; 
                q = q->next; 
            } 
        } 
    } 
    else if(lenone > lentwo) 
    { 
        p = headone; 
        for(int i=0; i<(lenone-lentwo); i++) 
        { 
            p = p->next; 
        } 
        LinkNode q = headtwo; 
        while( (NULL != p) && (NULL != q) ) 
        { 
            if(p == q) 
                return p; 
            else 
            { 
                p = p->next; 
                q = q->next; 
            } 
        } 
    } 
    else 
    { 
        p = headone; 
        LinkNode q = headtwo; 
        while( (NULL != p) && (NULL != q) ) 
        { 
            if(p == q) 
                return p; 
            else 
            { 
                p = p->next; 
                q = q->next; 
            } 
        } 
    } 
} 
 
 
LinkNode createLinkList(int n) 
{ 
    LinkNode h = NULL; 
    for(int i=0; i<n; i++) 
        h = insert(h, i+1); 
    return h; 
} 
 
void test() 
{ 
    head = createLinkList(10); 
    traverse(head); 
    printf("\n"); 
    LinkNode h = reverse(head); 
    LinkNode p = h; 
    traverse(h); 
} 
 
int main() 
{ 
    test(); 
    return 0; 
}