單連結清單操作（建立、列印、計算長度、插入指定位置節點、排序、析構、逆序輸出）...

struct node
{
    int val;
    node* next;
};

//此處需要注意,如果寫成void create(node* head,int n)
//這樣即使建立了連結清單，也沒有作用，因為node* head是形參
//在函數内部是對這個指針的拷貝進行操作,故不傳回連結清單
//正确形式應該是void create(node* &head,int n)
node* create(unsigned int n)
{
    node *head = new node;
    node *p = head, *q;
    head->val = rand() % RAND_MAX;
    cout << "建立節點:" << 0 << " 值:" << head->val << endl;

    for (size_t i = 1; i < n; i++)
    {
        q = new node;
        q->val = rand() % RAND_MAX;
        cout << "建立節點:" << i << " 值:" << q->val << endl;

        p->next = q; //連結清單疊加
        p = p->next;
    }
    p->next = NULL; //切記尾端處理

    return head;
}

void erase(node* head)
{
    if (NULL == head) return;

    node *tmp;
    while (head)
    {
        tmp = head;
        head = head->next;
        delete tmp;
    }
}

int getnodelen(node* head)
{
    int n = 0;
    node *temp=head;
    while (temp)
    {
        n++;
        temp = temp->next;
    }
    return n;
}

//此題原本做法出現兩處錯誤
//(1)void delnode(node* head, int num)，此處head傳遞進入的是指針的拷貝,如果頭節點被改變，就呵呵了
//(2)邏輯錯誤，原程式中隻若是頭節點相等，删除操作後就傳回了，這種考慮是不完全的
void delnode(node* &head, int num)
{
    if (NULL == head) return;

    node *temp, *p = head;

    //删除從頭節點連續相等數值
    while (head != NULL&&head->val == num)
    {
        temp = head;
        head = head->next;
        delete temp;
        cout << "删除頭節點，數值為：" << num << endl;
    }

    if (head) p = head;
    else return;

    while (p->next)
    {
        if (p->next->val == num)
        {
            temp = p->next;
            //錯誤寫成p = temp->next;
            p->next = temp->next;
            delete temp;
            cout << "删除節點，數值為：" << num << endl;
        }
        else
        {
            p = p->next;
        }
    }
}

//在連結清單中第i個位置插入節點，即在第i個節點前插入元素
bool insert_n_list(node* &head, int n, int num)
{
    if (n < 1 || head == NULL) return false;

    int i = 1;
    node *temp, *p = head;

    //插入頭節點
    if (n == 1)
    {
        temp = new node;
        temp->val = num;
        temp->next = head;
        head = temp;
        return true;
    }

    while (p != NULL&&i < n - 1)
    {
        ++i;
        p = p->next;
    }

    if (i == n - 1 && p != NULL) //尋找到插入節點
    {
        temp = new node;
        temp->val = num;
        temp->next = p->next;
        p->next = temp;
        return true;
    }
    else
    {
        return false;
    }
}

void printnodelist(node* head)
{
    if (NULL == head) return;

    node *temp = head;
    while (temp)
    {
        cout << " " << temp->val << "," ;
        temp = temp->next;
    }
    cout << endl;
}

//按升序排列（僅進行值交換，不進行指針交換）
void sort_nodelist(node* head)
{
    if (head == NULL || head->next == NULL)
        return;

    node *p = head;
    bool sign = false;
    int i, j, len = getnodelen(head), temp;

    for (i = len - 1; i > 0; i--)
    {
        sign = false;
        p = head;
        for ( j = 0; j < i; j++)
        {
            if (p->val>p->next->val)
            {
                sign = true;
                temp = p->val;
                p->val = p->next->val;
                p->next->val = temp;
            }
            p = p->next;
        }

        if (!sign) 
            break; //此趟排序未發生交換
    }
}

void reverse_nodelist(node* &head)
{
    //空連結清單或者單節點連結清單不進行轉置
    if (head == NULL || head->next == NULL)
        return;

    node *p1 = head, *p2 = head->next, *p3;

    while (p2)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }

    //此處需注意最後一個節點是NULL,隻有當P2為NULL時，轉置方才完成
    //此時将NULL，即P2後面的P1提取出來作為頭節點，轉置完成
    head->next = NULL;
    head = p1;
}      

2015年8月5号添加：

//可以調用遞歸做,但是如果連結清單較長,易導緻棧溢出
void print_reverse(node* list)
{
    if (NULL == list)
        return;

    //單節點單獨處理
    if (NULL == list->next)
    {
        cout << " " << list->val << endl;
        return;
    }

    node* temp;
    stack<int> print;
    while (NULL != temp)
    {
        print.push(temp->val);
        temp = temp->next;
    }

    int val;
    while (!print.empty()) //stack若為空,用empty判斷傳回true
    {
        val = print.top();
        cout << " " << val << ",";
        print.pop();
    }
    cout << endl;
}      

轉載于:https://www.cnblogs.com/jason1990/p/4702422.html