4.链表介绍与基本操作

这节就不逼逼那么多了，直接show code，个人感觉自己用代码实现一遍更好

/**********************************************************
 *  单链表的基本操作
 *  
 *  功能包含：
 *      节点的数据结构，链表遍历，节点的插入，节点的删除，
 *  链表冒泡排序，链表分割，归并排序
 *
 *********************************************************/

//数据结构
class node
{
    public:
        int data;
        node* next;
};


//链表遍历
void print (node* head) {
    for (node* p = head; p != NULL; p = p->next)
        cout << p->data;
    cout << endl;
}

int getLength (node* head) {
    int len = 0;
    while (head != NULL) {
        head = head->nex;
        len ++;
    }

    return len;
}


//插入节点

//插入到头部
void insertBegin (node*& head, int val) {
    node* newNode = new node();
    newNode->data = val;
    newNode->next = head;

    head = newNode;
}

//插入到尾部
void insertEnd (node*& head, int val) {
    node* newNode = new node();
    newNode->data = val;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
    }

    else {
        node* p = head;
        while (p->next != NULL)
            p = p->next;
        p->next = newNode;
    }
}

//在有序表中插入到指定位置
void insert (node*& head, int num) {
    node *cur = head, *pre = NULL;
    while (cur->data < num && pre->next != NULL)
        pre = cur, cur = cur->next;

    node* p = new node();
    p->data = num;

    //链表中的数据全部小于num
    if (cur->data < num) {
        cur->next = p;
        p->next = NULL;
    } 

    //链表中的数据全部大于num
    else if (cur == head) {
        p->next = cur;
        head = p;
    }

    //第三种情况：位于首尾之间,插入到previous和current中间
    else {
        pre->next = p;
        p->next = cur;
    } 
}


//删除节点
void remove (node*& head, int num) {
    node *cur = head, *pre = NULL;
    while (cur->data != num && cur->next != NULL) {
        pre = cur;
        cur = cur->next;
    }

    if (cur->data != num)
        cout << "Can't Found " << num <<endl;

    else {
        //删除头节点
        if (cur == head) {
            head = cur->next;
            delete cur;
        }
        
        //删除非头节点
        else {
            pre->next = cur->next;
            delete cur;
        }
    }

}



//经典O(n^2)的冒泡排序算法
 void bubbleSort (node* head) {
    int len = 0;
    for (node* p = head; p != NULL; p = p->next) {
        len ++;
    } 

    for (int i = 1; i < len; i++) {
        node* p = head;
        for(int j = 0; j < len - i; j++, p = p->next) {
            if (p->data > p->next->data)
            {
                int tem = p->data;
                p->data = p->next->data;
                p->next->data = tem;
            }

        }
    }

 }



//归并排序

node* mergesort(node *lsit1, node *list2)
{
    if (list1 == NULL) return list2;
    else if(list2 == NULL) return list1;

    node *result= new node(), *p = result;
    while (list1 != NULL && list2 != NULL)
        if (list1->data < list2->data)
            result->next = list1, result = list1, list1 = list1->next;
        else
            result->next = list2, result = lsit2, list2 = list2->next;
    if (list1 != NULL)  result->next = list1;
    if (list2 != NULL)  result->next = list2;


    //返回头节点
    result = p->next;
    delete p;
    return result;
}


//将链表分割为两个链表
//head:原链表
//list1,list2:分割后的两个链表

void split(node *head, node *&list1, node *&list2)
{
    if (head == NULL || head->next == NULL)
    {
        list1 = head, list2 = NULL;     return;
    }

    node *slow = head, *fast = head->next;
    while (fast != NULL)
    {
        fast = fast->next;
        if (fast != NULL)
            fast = fast->next, slow = slow->next;
    }
    list1 = head, list2 = slow->next;
    slow->next = NULL;
}


//归并排序主函数

void mergeSort(node *&head)
{
    if (head == NULL || head->next == NULL) 
        return;
    
    node *list1, *list2;
    split(head, list1, list2);
    mergeSort(list1);
    mergeSort(list2); 
    head = mergesort(list1, list2);
}