[数据结构与算法]链表c++构建与操作

数据结构C++实现：王道考研学习笔记—链表

顺序表：
优点：可随机存取，存储密度高
缺点：要求大片连续空间，改变容量不方便

链表：
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//链表节点结构
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* p) : val(x), next(p) {}
};

// 获取链表中第k个元素
ListNode* get(ListNode* &head, int i) {
	int j = 1;
	ListNode* p = head;
	if (i == 0) {
		return head;
	}
	if (i < 1) {
		return nullptr;
	}
	while (p != nullptr) {
		if (j == i) {
			break;
		}
		j++;
		p = p->next;
	}
	return p;
}

//头插法构建链表
ListNode* BuildHeadListNode(ListNode * head,vector<int> num) {
	for (auto it = num.rbegin(); it != num.rend(); ++it) {
		ListNode* p = new ListNode(*it, head->next);
		head->next = p;
	}
	return head;
}

//尾部插法构建链表
ListNode* BuildTailListNode(ListNode* head, const vector<int>& num) {
	ListNode* pre = head;
	for (auto it = num.begin(); it != num.end(); ++it) {
		ListNode* p = new ListNode(*it,nullptr);
		pre->next = p;
		pre = p;
	}
	return head;
}

//倒数第k个节点
ListNode* getKthFromEnd(ListNode* head, int k) {
	ListNode* fp = head;
	ListNode* sp = head;
	while (fp != nullptr && k--) {
		fp = fp->next;
	}
	while (fp != nullptr) {
		fp = fp->next;
		sp = sp->next;
	}
	return sp;
}

//从头到尾打印链表
void printListNode(ListNode* head) {
	while (head != nullptr) {
		cout << head->val << " ";
		head = head->next;
	}
}


//从尾到头打印链表
void reprintListNode(ListNode* head) {
	if (head == nullptr) {
		return;
	}
	reprintListNode(head->next);
	cout << head->val << " ";
}

//反转链表
ListNode* reverseList(ListNode *head) {
	ListNode* cur = head;
	ListNode* pre = nullptr;
	while (cur != nullptr) {
		ListNode* next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = cur->next;
	}
	return pre;
}
int main() {
	vector<int> v = {1,2,3,4,5};
	ListNode* head = new ListNode();

	head = BuildHeadListNode(head, v);
	//head = BuildTailListNode(head, v);
	head = head->next;

	int i = 1;
	ListNode* p = get(head, i);
	cout << "获取第"<< i<<"个点的元素"<< endl;
	if (p != nullptr) {
		cout << p->val << endl;
	}
	else {
		cout << "-1" << endl;
	}

	cout << "倒数第k个节点："<< endl;
	cout << getKthFromEnd(head, 1)-> val << endl;
	cout << "从头到尾打印链表" << endl;
	printListNode(head);
	cout << endl;

	cout << "从尾到头打印链表" << endl;
	reprintListNode(head);
	cout << endl;

	//反转链表
	cout << endl;
	reverseList(head);
	printListNode(head);
	cout << endl;

	return 0;
}