部分链表操作总结

  1. 云栖社区>
  2. 博客列表>
  3. 正文

部分链表操作总结

shy丶gril 2016-05-18 11:50:15 浏览303 评论0

摘要: 部分链表操作总结 #include <iostream> #include <cstdlib> using namespace std; // definition of Node struct Node { int val; Node *next; Node(int x...

部分链表操作总结

#include <iostream>
#include <cstdlib>
using namespace std;

// definition of Node
struct Node
{
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL){}
};

// create a linklist with n nodes
Node* create(int n)
{
    Node *head = new Node(rand() % 100);
    Node *pre = head;
    for (int i = 1; i < n; i++)
    {
        Node *newnode = new Node(rand() % 100);
        pre->next = newnode;
        pre = newnode;
    }

    return head;
}

// insert node with value num
Node* insert(Node *head, int num)
{
    Node *p = head;
    Node *q;
    while (p != NULL && p->val < num)
    {
        q = p;
        p = p->next;
    }

    Node *newnode = new Node(num);
    if (p == head)
    {
        newnode->next = head;
        head = newnode;
    }
    else if (p == NULL)
    {
        q->next = newnode;
    }
    else
    {
        newnode->next = q->next;
        q->next = newnode;
    }

    return head;
}

// delete node with value num
Node* del(Node *head, int num)
{
    Node *p = head;
    Node *q;
    while (p != NULL && p->val != num)
    {
        q = p;
        p = p->next;
    }

    if (p == head)
    {
        head = head->next;
        delete p;
    }
    else if (p == NULL)
    {
        cout<<"Node could not found!"<<endl;
    }
    else
    {
        q->next = q->next->next;
        delete p;
    }

    return head;
}

int length(Node *head)
{
    int len = 0;
    while (head != NULL)
    {
        ++len;
        head = head->next;
    }

    return len;
}

// sort the linklist
Node* sort(Node *head)
{
    int n = length(head);
    for (int i = 0; i < n - 1; i++)
    {
        Node *p = head;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (p->val > p->next->val)
            {
                int temp = p->val;
                p->val = p->next->val;
                p->next->val = temp;
            }
            p = p->next;
        }
    }

    return head;
}

// reverse the linklist non-recursive
Node *reverse(Node *head)
{
    if (head == NULL)
    {
        return head;
    }

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

    return head;
}

// reverse the linklist recursively
Node* reverse2(Node *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    Node *newhead = reverse2(head->next);
    head->next->next = head;
    head->next = NULL;

    return newhead;
}

void print(Node *head)
{
    while (head != NULL)
    {
        cout<<head->val<<" ";
        head = head->next;
    }
    cout<<endl;
}

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

int main()
{
    Node *head = create(10); print(head);
    sort(head); print(head);
    head = insert(head, 101); print(head);
    head = insert(head, -1); print(head);
    head = insert(head, 50); print(head);
    head = del(head, -1); print(head);
    head = del(head, 101); print(head);
    head = del(head, 50); print(head);
    head = reverse(head); print(head);
    head = reverse2(head); print(head);
    droplist(head);
}


转载:http://blog.csdn.net/foreverling/article/details/46970981

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

shy丶gril
文章2082篇 | 关注205
关注
操作审计(ActionTrail)会记录您的云账户资源操作,提供操作记录查询,并可以将记录文... 查看详情
作为阿里云数据存储产品体系的重要组成部分,致力于提供低成本、高可靠的数据归档服务,适合于海量... 查看详情
大数据商业智能套件提供海量数据实时在线分析,拖拽式操作、丰富的可视化效果,帮助您轻松自如地完... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航