链表随笔之单链表

链表是笔试面试经常考的内容，这次没有看书，完全按照自己的思路完成链表基本实现。

1. 单链表的创建

 这里之前由于申请连续空间导致不可预见的错误，感谢花花帮我指出错误。

struct Node 
{
    int val;
    Node * next;
};
Node* creat_list(int n)            //创建单链表 n为元素个数
{
    Node* head = NULL;
    Node* head_temp = NULL;
    if (n > 0)
    {
        head = new Node;
        head_temp = head;        //保存头元素
        head->val = rand()%100;
        int num = n - 1;
        while (num--)
        {
            Node* tem = new Node;
            tem->next = NULL;
            tem->val = rand()%100;
            head->next = tem;
            head = tem;
        }
    }
    return head_temp;
}

2. 单链表的删除

void del(Node * head)
{
    Node* temp = NULL;
    while (head != NULL)
    {
        temp = head->next;
        delete head;
        head = temp;
    }
}

3. 单链表的长度和输出

int len(Node * head)
{
    Node* temp = head;
    int leng = 0;
    while (temp != NULL)
    {
        ++leng;
        temp = temp->next;
    }
    return leng;
}
void dis(Node* head)
{
    Node* temp = head;
    if (temp == NULL)
    {
        cout<<"NULL"<<endl;
        return;
    }
    while (temp != NULL)
    {
        cout<<temp->val<<' ';
        temp = temp->next;
    }
    cout<<endl;
}

4 . 单链表元素的插入和删除

void del_node(Node* &head,int n)
{
    Node* temp = head;
    Node* pre = NULL;
    Node* nex = NULL;
    if (head == NULL)
    {
        return;
    }
    while (temp != NULL)
    {
        nex = temp->next;
        if (temp->val == n) 
        {
            if (temp == head)     //删除头元素
            {
                head = nex;
                delete temp;
            }
            else             //非头元素
            {
                pre->next = nex;
                delete temp;        
            }
            return;
        }
        else
        {
            pre = temp;
            temp = temp->next;
        }
    }
}
void add_node(Node* &head,int n,int pos)  //链表头  元素值  位置
{
    if (pos > len(head) + 1||pos < 1)
    {
        return;
    }
    Node* new_one = new Node;
    new_one->val = n;
    if (pos == 1)          //加在链表头
    { 
        new_one->next = head;
        head = new_one;
    }
    else            
    {
        Node* temp = head;
        for (int i = 2 ; i < pos;++i)         //找到要插入的位置
        {
            temp = temp->next;
        }
        Node* temp2 = temp->next;            //保存插入位置后的第一个元素
        temp->next = new_one;
        new_one->next = temp2;
    }
    //dis(head);
}

5. 单链表的逆置 

Node* fanxu(Node* head)
{
    Node* pre = NULL;
    Node* nex = NULL;
    while (head != NULL)
    {
        nex = head->next;
        head->next = pre;
        pre = head;
        head = nex;
    }
    return pre;
}

6. 单链表应用 找其排在中间的数

思想： 设置两个结点，一个结点每次走一步，另一个结点每次走两步，这样当后者走到末尾的时候，前者正好走到中间位置。

还有很多这类的变种，比如求单链表倒数第n个数之类的，解决方案都是用两个结点，并行走，中间差多少步就行了。

int find_mid(Node* head)
{
    int leng = len(head);
    Node* temp1 = head;
    Node* temp2 = head->next;
    bool jiou = true;               //确定奇偶步，决定temp1走还是不走
    while (temp2 != NULL)          //temp2没有走到末尾
    {
        temp2 = temp2->next;
        if (!jiou)
        {
            temp1 = temp1->next;
            jiou = true;          //间隔步设置
        }
        else
        {
            jiou = false;
        }
    }
    if (leng%2 == 0)             //如果为偶数 则为中间两个数的平均数
    {
        return (temp1->val+temp1->next->val)/2.0;
    }
    else
    {
        return temp1->val;
    }
}