内容纲要
  • 实现带头结点(注意:不是头指针)的链表,并利用带头节点的链表实现以下功能:
    链表有序插入
    链表合并:写一个方法,传入两个有序链表(按升序),返回一个合并后的有序链表(按升序)
    链表分隔:传入一个数字链表,按照奇偶性,拆分为奇数链表和偶数链表
    链表就地逆置:将一个链表逆序
#include "pch.h"
#include <iostream>
using namespace std;

struct Node
{

    Node(int data)
    {
        this->data = data;
        this->next = nullptr;
    }
    int data;
    Node* next;
};

class linklist
{
private:
    Node*head;
public:

    linklist()
    {
        head = new Node(NULL);
        head->next=NULL;
    };

    Node* Insert(int index, int data) {
        if (head == nullptr)
        {
            head = new Node(data);
            return head;
        }
        if (index == 0)
        {
            Node * pnew = new Node(data);
            Node * P = head;
            head = pnew;
            head->next = P;
            return pnew;
        }
        int cnt = 0;
        for (Node* p = head; p != nullptr; p = p->next)
        {
            if (cnt == index - 1)
            {
                Node* p2 = p->next;
                Node*pnew = new Node(data);
                p->next = pnew;
                pnew->next = p2;
                return pnew;
            }
            cnt++;
        }
        return nullptr;
    }

    Node* sort_insert(int data)//按升序插入
    {
        for (Node* p=head;p!=nullptr;p=p->next)
        {
            if (p->next==nullptr||p->next->data>data)
            {
                Node* pnew = new Node(data);
                Node* p1 = p->next;
                p->next = pnew;
                pnew->next = p1;
                return pnew;
            }
        }
        delete pnew;
        return nullptr;
    }

    void Merge(linklist &kk)// 把2个升序链表合并成一个升序链表
    {
        Node*p1 = this->head;
        Node*p2 = kk.head;
        while(p1&&p2)
        {
            if (p1->next==nullptr||p1->data>p2->data)
            {
                Node*Pnew = p1->next;
                p1->next = p2->next;
                p2->next = Pnew;

            }
        }
    }

    void Separate(linklist &ll,linklist &uu)// 把一个链表分割成2个,一个是奇数链表,一个是偶数链表,
    {
        Node* p1 = ll.head; Node* p2 = uu.head;
        while (head->next==NULL)
        {
            Node*px = head->next->next;
            if (head->next->data%2==0)
            {
                p1->next = head->next;
                p1 = p1->next;
                p1->next = NULL;
            }
            else
            {
                p2->next = head->next;
                p2 = p2->next;
                p2->next = NULL;
            }
        }
    }

    void Inversion()// 链表就地逆置,
    {
        Node* p = head->next;
        for (Node*p=head;p!=nullptr;p=p->next)
        {
            Node*p2 = p->next->next;
            Node*p3 = head->next;
            head->next = p->next;
            head->next->next = p3;
            p->next = p2;

        }
    }
};

发表评论