刷leetcode设计一个链表，大三准备找实习刷点基础算法--

笨笨猪

今天在leetcode刷到两道链表逆置题

（1：全部逆置；2部分逆置）

看到很多校招笔试题上也有很多涉及到链表的，就今天设计了一个单链表的类玩玩

大佬轻喷，很多地方没有优化，有指点的地方感激不尽

头文件.h

[C++] 纯文本查看 复制代码

#pragma once
#include"iostream"
#include <cstdlib>
#include <time.h>
using namespace std;

struct Node
{
        int val;
        Node *next;
        Node(int nVal, Node *nNext = NULL) {
                val = nVal;
                next = nNext;
        }
        Node() {}
};

class ListNode
{
private:
        Node *head;  //声明头节点
        int counts;

public:
        ListNode();
        ~ListNode();
        void CreateList(int n);
        void CreateListByPC(int n,int randnum);
        ListNode* Reverse();
        ListNode* ReverseBetween(int m, int n);
        void ShowList();
        int ListLength();
        void InsertNode(int position, int value);
        void DeleteNode(int position);
        Node *GetNodeByPosition(int position);
};[/align][align=center]

源文件

[C++] 纯文本查看 复制代码

#include "ListNode.h"


ListNode::ListNode()
{
        head = new Node;
        head->next = NULL;
        head->val = 0;
}

ListNode::~ListNode()
{
        Node * temp = head;        //创建一个临时变量保存删除节点信息
        while(head->next){
                temp = head->next;
                delete head;
                head = temp;
        }
        delete head;
        cout << "该链表析构完成..." << endl;
}

void ListNode::CreateList(int n)
{
        cout << "正在创建长度为" << n << "的链表......" << endl;
        Node *preNode = head;
        for (int i = 0; i < n; i++)
        {
                Node *newNode = new Node;
                cout << "请输入该节点的值: ";
                cin >> newNode->val;
                newNode->next = NULL;
                preNode->next = newNode;
                preNode = newNode;
        }
}

void ListNode::CreateListByPC(int n, int randnum)
{
        cout << "正在创建长度为" << n << "的链表，其值范围为:" << randnum << endl;
        srand((unsigned int)time(NULL));
        Node *preNode = head;
        for (int i = 0; i < n; i++)
        {
                Node *newNode = new Node;
                newNode->val = rand()%randnum;
                newNode->next = NULL;
                preNode->next = newNode;
                preNode = newNode;
        }
}

ListNode * ListNode::Reverse()
{
        cout << "正在逆置链表..." << endl;
        Node *newHead = NULL;                        //临时变量，遍历新链表
        Node *vNode = head->next;                //取第一个节点开始遍历
        while (vNode!=NULL)
        {
                Node *temp = vNode->next;        //备份原链表的下一个节点信息
                vNode->next = newHead;                //当前节点的指针域修改
                newHead = vNode;
                vNode = temp;
        }
        head->next = newHead;
        return NULL;
}

ListNode * ListNode::ReverseBetween(int m,int n)
{
        if (m <= 0 || n >= this->counts)
                return false;
        Node *temp = head;                                //临时变量保存头节点
        int changeLength = n - m + 1;        //获取需要逆置的个数

        while (--m)
        {
                temp = temp->next;
        }

        Node *preNode = temp;                //找到m节点的前置节点
        temp = temp->next;
        Node *changeTail = temp;        //m节点,即需要改变的尾节点
        Node *newHead = NULL;
        

        cout << "changeLength = " << changeLength << endl;

        int i = 0;
        while (changeLength--)
        {
                cout << "正在执行第" << ++i << "ci" << endl;
                Node *vNode = temp->next;        //备份下一个节点的信息
                temp->next = newHead;
                newHead = temp;
                temp = vNode;
        }

        preNode->next = newHead;
        changeTail->next = temp;
        return NULL;
}

void ListNode::ShowList()
{
        Node *tempNode = head;
        while (tempNode->next)
        {
                cout << tempNode->next->val <<"\t";
                tempNode = tempNode->next;
        }
        cout << endl << "该链表已显示完毕..." << endl;
}

int ListNode::ListLength()
{
counts = 0;//初始化为0，不然会重复自增
        Node *temp = head;
        for (; temp->next != NULL; temp = temp->next)
                counts++;
        return counts;
}

void ListNode::InsertNode(int position, int value)
{
        Node *temp = this->GetNodeByPosition(position - 1);
        Node *newNode = new Node(value);
        newNode->next = temp->next;
        temp->next = newNode;
}

void ListNode::DeleteNode(int position)
{
        if (position<1 || position>this->ListLength())
                return;
        Node *temp = this->GetNodeByPosition(position - 1);
        Node *delNode = temp->next;
        temp->next = delNode->next;
        delete delNode;
}

Node * ListNode::GetNodeByPosition(int position)
{
        if (position<1 || position>this->ListLength())
                return flase;

        Node *temp = head;
        for (int i = 0; i < position; i++)
                temp = temp->next;
        return temp;
}