单链表操作总结

最近工作涉及到很多链表操作，就把它笼统的复习了一遍。
常规的链表操作：

typedef struct _LIST_NODE_T
{
    void *data;
    struct _LIST_NODE_T *next;
}LIST_NODE_T;

1.链表逆序

//已知链表的头节点，将链表逆序----单向链表逆序
LIST_NODE_T resever_list(LIST_NODE_T *head)
{
    if(head == NULL || head->next == NULL)
        return head;

    LIST_NODE_T *p1 = head;
    LIST_NODE_T *p2 = p1->next;
    LIST_NODE_T *p3 = p2->next;

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

2.找出链表的中间元素。----一个值得学习的方法。效率o(∩_∩)o 

//找出链表的中间元素
LIST_NODE_T* find_midlist(LIST_NODE_T* head)
{
    if(head == NULL || head->next == NULL)
        return head;
    LIST_NODE_T *p1, *p2;
    p1 = p2 = head;
    while(1)
    {
     if(p2->next != NULL && p2->next->next != NULL)
     {
            p1 = p1->next;
            p2 = p2->next->next;
     }
        else
            break;
    }
    return p1;
}

3.将两个有序的链表合并成一个---常规方法

//已知两个链表的head1 和head  各自有序。要求将其合并成一个链表依然有序
LIST_NODE_T* merge(LIST_NODE_T *head1, LIST_NODE_T *head2, int (*pCmpFunc)(void*, void*))
{
    if(head1 == NULL)
        return head2;
    else if(head2 == NULL)
        return head1;

    if(pCmpFunc == NULL)
        return NULL;

    LIST_NODE_T *head;
    LIST_NODE_T *cur;
    LIST_NODE_T *p1;
    LIST_NODE_T *p2;

    if(pCmpFunc(head1->data, head2->data) < 0)
    {
        head = head1;
        p1 = head1->next;
        p2 = head2;
    }
    else
    {
        head = head2;
        p2 = head2->next;
        p1 = head1;
    }
    cur = head;
    while(p1 != NULL && p2 != NULL)
    {
     if(pCmpFunc(p1->data, p2->data) < 0)
     {
            cur->next = p1;
            cur = p1;
            p1 = p1->next;
     }
        else
        {
            cur->next = p2;
            cur = p2;
            p2 = p2->next;
        }
    }
    if(p1 == NULL)
        cur->next = p2;
    else if(p2 == NULL)
        cur->next = p1;

    return head;
}

4，将两个有序的链表合并成一个----递归方法

LIST_NODE_T* mergeRecursive(LIST_NODE_T *head1, LIST_NODE_T *head2, int (*pCmpFunc)(void*, void*))
{
    if(head1 == NULL)
        return head2;
    if(head2 == NULL)
        return head1;

    LIST_NODE_T *head = NULL;
    if(pCmpFunc(head1->data, head2->data) < 0)
    {
        head = head1;
        head1->next = mergeRecursive(head1->next, head2, pCmpFunc);
    }
    else
    {
        head = head2;
        head2->next = mergeRecursive(head1, head2->next, pCmpFunc);
    }
    return head;
}

5.删除链表中的某个节点

//只给定单链表某个节点p.删除该节点
void deleNode(LIST_NODE_T *pNode, void (*pFreeFunc)(void *))
{
    if(pNode == NULL)
        return;
    if(pNode->next == NULL)
    {
     if(pFreeFunc != NULL)
            pFreeFunc(pNode->data);
        delete pNode;
        pNode = NULL;
        return;
    }

    LIST_NODE_T pNodeNext = pNode->next;
    pNode->data = pNodeNext->data;
    pNode->next = pNodeNext->next;

    if(pFreeFunc != NULL)
        pFreeFunc(pNodeNext->data);
    delete pNodeNext;
    pNodeNext = NULL;
    return;
}

6.在某个节点前插入元素

//只给定单链表中某个节点p。 在p前面插入节点
void insertNode(LIST_NODE_T *pNode, void *data)
{
    if(pNode == NULL)
        return;

    LIST_NODE_T *pNewNode;
    pNewNode = new LIST_NODE_T();
    if(pNewNode == NULL)
    {
        std::cout<<"create new node error"<<std::endl;
        return;
    }
    LIST_NODE_T *pNodeNext = pNode->next;
    pNode->next = pNewNode;
    pNewNode->next = pNodeNext;

    pNewNode->data = pNode->data;
    pNode->data = data;
}

7.给定单链表头节点，删除链表中倒数第k  个节点

//给定单链表头节点，删除链表中倒数第k  个节点
void deleNode1(LIST_NODE_T * phead, int nReserverK, void(* pFreeFunc)(void *))
{
    if(phead == NULL)
        return;

    LIST_NODE_T *p1, *p2;
    p1 = p2 = phead;
    for(int i=1; i<=nReserverK; i++)
    {
        p2 = p2->next;
        if(p2 == NULL && i!=nReserverK)
        {
            return;
        }
    }
    while(p2 != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    deleNode(p1, pFreeFunc);
}