数据结构与算法学习（4）

一.排序算法总结

1.选择排序：时间O(n^2) 空间O(1) 不稳定
2.冒泡排序：时间O(n^2) 空间O(1) 稳定
3.插入排序：时间O(n^2) 空间O(1) 稳定
4.快速排序：时间O(nlogⁿ) 空间O(logⁿ) 不稳定
5.归并排序：时间O(nlogⁿ) 空间O(N) 稳定
6.堆排序：时间O(n*logⁿ) 空间O(1) 不稳定

二.哈希表和有序表

1.哈希表操作O(1)
2.有序表操作O(logⁿ)

三.链表

1.单链表反转

ListNode* ReverseList(ListNode* head) {
	ListNode* prev = nullptr;
	ListNode* next = nullptr;
	while (head)
	{
		next = head->next;
		head->next = prev;
		prev = head;
		head = next;
	}
	return prev;
}

2.双链表反转

DoubleNode* DoubleReverseList(DoubleNode* head) {
	DoubleNode* prev = nullptr;
	DoubleNode* next = nullptr;
	while (head)
	{
		next = head->next;
		head->next = prev;
		head->prev = next;
		prev = head;
		head = next;
	}
	return prev;
}

3.判断回文链表

1. 利用整个Stack

bool HuiWenList01(ListNode* head) {
	stack<int> s;
	ListNode* tmp = head;
	while (tmp)
	{
		s.push(tmp->val);
		tmp = tmp->next;
	}
	tmp = head;
	while (!s.empty())
	{
		int val = s.top();
		if (tmp == nullptr || val != tmp->val)
			return false;
		s.pop();
		tmp = tmp->next;
	}
	return true;
}

2. 利用半个Stack

bool HuiWenList02(ListNode* head) {
	ListNode* fast = head;
	ListNode* slow = head->next;
	stack<int> s;
	while (fast->next != nullptr && fast->next->next != nullptr)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	while (slow)
	{
		s.push(slow->val);
		slow = slow->next;
	}
	ListNode* tmp = head;
	while (!s.empty())
	{
		if (tmp == nullptr || tmp->val != s.top())
			return false;
		tmp = tmp->next;
		s.pop();
	}
	return true;
}

3. 不利用额外空间

bool HuiWenList03(ListNode* head) {
	ListNode* fast = head;
	ListNode* slow = head;
	while (fast->next != nullptr && fast->next->next != nullptr)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	fast = slow->next;
	slow->next = nullptr;
	ListNode* tmp = nullptr;
	while (fast)
	{
		tmp = fast->next;
		fast->next = slow;
		slow = fast;
		fast = tmp;
	}
	tmp = slow;
	fast = head;
	bool res = true;
	while (fast != nullptr && slow != nullptr)
	{
		if (fast->val != slow->val) {
			res = false;
			break;
		}
		fast = fast->next;
		slow = slow->next;
	}
	slow = tmp->next;
	tmp->next = nullptr;
	while (slow)
	{
		fast = slow->next;
		slow->next = tmp;
		tmp = slow;
		slow = fast;
	}
	return res;
}

4.小于某数放链表左边，等于放中间，大于放右边

ListNode* Test01(ListNode * head,int num) {
	ListNode* leftStart = nullptr;
	ListNode* leftEnd = nullptr;
	ListNode* conStart = nullptr;
	ListNode* conEnd = nullptr;
	ListNode* rightStart = nullptr;
	ListNode* rightEnd = nullptr;
	ListNode* tmp = nullptr;
	while (head)
	{
		tmp = head->next;
		head->next = nullptr;
		if (head->val < num) {
			if (leftStart == nullptr) {
				leftStart = head;
				leftEnd = head;
			}
			else {
				leftEnd->next = head;
				leftEnd = head;
			}
		}
		else if (head->val == num) {
			if (conStart == nullptr) {
				conStart = head;
				conEnd = head;
			}
			else {
				conEnd->next = head;
				conEnd = head;
			}
		}
		else {
			if (rightStart == nullptr) {
				rightStart = head;
				rightEnd = head;
			}
			else {
				rightEnd->next = head;
				rightEnd = head;
			}
		}
		head = tmp;
	}

	//串起来
	if (leftEnd != nullptr) {
		leftEnd->next = conStart;
		conEnd = conEnd == nullptr ? leftEnd : conEnd;
	}

	if (conEnd != nullptr) {
		conEnd->next = rightStart;
	}

	return leftStart != nullptr ? leftStart : (conStart != nullptr ? conStart : rightStart);
}

5.Copy Rand拷贝随机链表

1.使用哈希表实现

RandListNode* CopyTest(RandListNode* head) {
	unordered_map<RandListNode*, RandListNode*> hasTable;
	RandListNode* tmp = head;
	while (tmp)
	{
		hasTable.insert(tmp, new RandListNode(tmp->val));
		tmp = tmp->next;
	}
	tmp = head;
	while (tmp)
	{
		hasTable[tmp]->next = hasTable[tmp->next];
		hasTable[tmp]->rand = hasTable[tmp->rand];
		tmp = tmp->next;
	}
	return hasTable[head];
}

2.不借助额外空间实现

RandListNode* CopyTest02(RandListNode* head) {
	RandListNode* curr = head;
	RandListNode* next = nullptr;
	while (curr)
	{
		next = curr->next;
		curr->next = new RandListNode(curr->val);
		curr->next->next = next;
		curr = next;
	}
	curr = head;
	RandListNode* copyNode = nullptr;
	while (curr)
	{
		next = curr->next->next;
		copyNode = curr->next;
		copyNode->rand = curr->rand == nullptr ? nullptr : curr->rand->next;
		curr = next;
	}
	RandListNode* resNode = head->next;
	curr = head;
	while (curr)
	{
		next = curr->next->next;
		copyNode = curr->next;
		curr->next = next;
		copyNode->next = next == nullptr ? nullptr : next->next;
		curr = next;
	}
	return resNode;
}