刷leetcode设计一个链表，大三准备找实习刷点基础算法--
本帖最后由 笨笨猪 于 2019-2-26 19:26 编辑今天在leetcode刷到两道链表逆置题{:301_996:}
（1：全部逆置；2部分逆置）
看到很多校招笔试题上也有很多涉及到链表的，就今天设计了一个单链表的类玩玩
大佬轻喷，很多地方没有优化，有指点的地方感激不尽{:301_978:}
头文件.h
#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);
};
源文件
#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;
}
页:
[1]