[数据结构与算法]链表及相关操作

链表

建立一个链表

#include<stdio.h>

struct ListNode{
	int val;
	ListNode *next;
}; 

int main() {
	// 创建链结 
	ListNode a;
	ListNode b;
	// 赋值 
	a.val = 10;
	b.val = 20;
	// 连接 
	a.next = &b;
	b.next = NULL;
	// 遍历 
	ListNode *head = &a;
	while(head) {
		printf("%d\n", head->val);
		head = head->next;
	}
	return 0;
}

链表逆序 1

用一个新的头节点移动，对每一个节点进行修改

#include<stdio.h>

struct ListNode{
	int val; // data 数据域 
	ListNode *next; // 指针域 
	ListNode(int x) : val(x), next(NULL) {}
	// 赋值 val = x; next = NULL 
}; // 构造函数 

class Solution {
public:
	ListNode* reverseList(ListNode* head){
		ListNode *new_head = NULL;
		while(head) {
			ListNode *next = head->next; // 备份 
			head->next = new_head; // 将head 的指针指向new(即上一个节点) 
			new_head = head; // 让new 指向当前节点 
			head = next; // 开始对下一个节点进行操作 
		} 
		return new_head;
	} // 返回列表逆序后的头节点指针 
};

int main() {
	ListNode a(1);
	ListNode b(2);
	ListNode c(3);
	a.next = &b;
	b.next = &c;
	Solution solve;
	ListNode *head = &a;
	while(head) {
		printf("%d\n", head->val);
		head = head->next;
	}
	head = solve.reverseList(&a);//传递头指针
	while(head){
		printf("%d\n", head->val);
		head = head->next;
	}
	return 0;
}

链表局部逆序（m~n）

多记录一个前驱节点pre_head、修改后的局部首（new_head）尾（modify_list_tail）节点

#include<stdio.h>
// 局部逆序 
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x): val(x), next(NULL) {} 
};

class Solution {
public:
	ListNode* reverseBetween(ListNode* head, int m, int n) {
		int cheng_len = n-m+1;
		ListNode *pre_head = NULL;
		ListNode *result = head;
		while(head && --m) {
			pre_head = head;
			head = head->next;
		}
		ListNode *modify_list_tail = head;
		ListNode *new_head = NULL;
		while(head && change_len) {
			ListNode *next = head->next;
			new_head = head;
			head->next = new_head;
			head = next;
			chenge_len--;
		}
		modify_list_tail->next = head;
		if(pre_head){
			pre_head->next = new_head;
		}
		else{
			result = new_head;
		}
		return result;
	}
}; 

int main() {
	...
	return 0;
} 

查找两个链表相交的第一个元素

思路一 ： 集合set

时间 O（nlogn）
空间 O(n)

#include<stdio.h>
// 思路一：set 求交集 
struct ListNode {
	int val;
	ListNode *next;
	ListNode int(x): val(X), next(NULL) {}
};

class Solution{
public:
	listNode *getIntersectionNode(ListNode *headA, ListNode *headB){
		std::set<ListNode> node_set;
		while(headA){ // 将链表1导入集合 
			node_set.insert(headA);
			headA = headA->next;
		}
		while(headB){ // 在集合中查找链表2的元素 
			if(node_set.find(headB) != node_set.end()){ //  查找结果不为空 
				headB = headB->next; 
			}
			headB = headB->next;
		}
		return NULL;
	}
};

int main() {
	...
	return 0;
}

思路二 ： 将L1 L2先遍历至较长链表的剩余节点与较短链表的长度相等，同时移动至相同节点

时间 O(n)
空间 O(1)

#include<stdio.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode (int x): val(x), next(NULL) {}
};

int getlen(ListNode *head){
	int len = 0;
	while(head){
		len ++;
		head = head->next;
	}
	return len;
}

ListNode forward_long(len_long, len_short, ListNode *head){
	delta = len_long - len_short;
	while(head && delta){
		delta--;
		head = head->next;
	}
	return head;
}

class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
		int list_A_len = getlen(headA); // 获取链表长度 
		int list_B_len = getlen(headB);
		if(list_A_len > list_B_len){
			headA = forward_long(list_A_len, list_B_len, headA);
		}
		else {
			headB = forward_long(list_B_len, list_B_len, headB);
		}
		while(headA && headB){
			if(headA == headB){ // 找到了输出答案 
				return headA;
			}
			headA = headA->next;
			headB = headB->next;  
		}
		return NULL; // 找不到输出 NULL 
	}
};

== 加几个样例试试 ==

#include<stdio.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode (int x): val(x), next(NULL) {}
};

int getlen(ListNode *head){
	int len = 0;
	while(head){
		len ++;
		head = head->next;
	}
	return len;
}

ListNode *forward_long(int len_long, int len_short, ListNode *head){
	int delta = len_long - len_short;
	while(head && delta){
		delta--;
		head = head->next;
	}
	return head;
}

class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
		int list_A_len = getlen(headA); // 获取链表长度 
		int list_B_len = getlen(headB);
		if(list_A_len > list_B_len){
			headA = forward_long(list_A_len, list_B_len, headA);
		}
		else {
			headB = forward_long(list_B_len, list_B_len, headB);
		}
		while(headA && headB){
			if(headA == headB){ // 找到了输出答案 
				return headA;
			}
			headA = headA->next;
			headB = headB->next;  
		}
		return NULL; // 找不到输出 NULL 
	}
};

int main(){
	ListNode a1(1);
	ListNode a2(2);
	ListNode a3(3);
	ListNode b1(4);
	ListNode b2(3);
	ListNode c1(5);
	ListNode c2(6);
	a1.next = &a2;
	a2.next = &a3;
	a3.next = &c1;
	c1.next = &c2;
	b1.next = &b2;
	b2.next = &c1;
	c1.next = &c2;
	Solution solve;

	ListNode *result = solve.getIntersectionNode(&a1, &b1);
	printf("%d\n", result->val);
	return 0;
} 

链表求环

思路一： set查找

#include<stdio.h>

struct List{
	int val;
	List *next;
	List(int x): val(x), next(NULL);
};

class Soultion{
public:
	ListNode *detectCycle(List *head){
		std::set<List *> node_set;
		while(head) {
			if(node_set.find(head) != node_set.end()){
				return head;
			}
			set.insert(head);
			head = head->next;
		} 
		return NULL; 
	}
};

思路二： 快慢指针赛跑

有环的话，跑的快的可以追上跑的慢的

#include<stdio.h>
#include<iostream>
using namespace std;
struct List{
	int val;
	List *next;
	List(int x): val(x), next(NULL){}
};

class Solution{
public:
	List *detectCycle(List *head){
		List *fast = head; // fast 一次跳两步 
		List *slow = head; // slow 一次跳一步 
		List *meet = NULL; // 相遇节点 
		while(fast){
			slow = slow->next;
			fast = fast->next;
			if(!fast){
				return NULL;
			}
			fast = fast->next;
			if(fast == slow){
				meet = fast;
				break;
			}
		}
		if(meet == NULL) {
			return NULL;
		}
		while(head && meet){
			if(head == meet) return head;
			head = head->next;
			meet = meet->next;
		}
		return NULL; // 返回进入公共环的第一个节点 
	}
};

int main(){
	List a(1);
	List b(2);
	List c(3);
	List d(4);
	List e(5);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	e.next = &c;
	Solution solve;
	List *node = solve.detectCycle(&a);
	if(node){
		cout << node->val << endl;
	}
	else cout << "NULL";
	return 0;
} 

链表划分

用两个临时节点将链表分为两段

#include<stdio.h>
struct List{
	int val;
	List *next;
	List(int x): val(x), next(NULL);
};

class Solution{
public:
	List *partition(List* head, int x){
		List less_head(0);
		List more_head(0);
		List *less_ptr = &less_head;
		List *more_ptr = &more_head; // 从空节点开始往后接 
		while(head){
			if (head->val < x){ // 小于x，依次接到less_ptr 后面 
				less_ptr->next = head;
				less_ptr = head;
			}
			else{ // 大于x，依次接到more_ptr 后面 
				more_ptr->next = head;
				more_ptr = head;
			}
			head = head->next;
		}
		less_ptr->next = more_head.next;
		more_ptr.next = NULL;
	}
	return less_ptr;
};

int main() {
	
	return 0;
} 

复杂链表的深度拷贝（两链表互相独立）

一个节点要对应两个指针，一个顺序指针和一个随机指针
难点：随机指针的对应，用两个map，一个从地址映射向指针的编号，另一个从指针的编号映射到地址（可用vector替代）

#include<stdio.h>
#include<map>

struct RandomListNode{
	int val;
	List *next, *random;
	List(int x): val(x), next(NULL), random(NULL);
}; 

class Solution{
public:
	RandomListNode *copyRandomLsit(RandomListNode *head) {
		std::map<RandomListNode *, int> node_map;
		std::vector<RandomLostNode *> node_vec;
		RandomListNode *ptr = head;
		int i = 0;
		while(ptr) {
			node_vec.push_back(new RandomListNode(ptr->label)); // 编号对应节点地址 
			node_map[ptr] = i; // 地址对应节点编号 
			ptr = ptr->next;
			i++;
		}
		node_vec.push_back(0); // 使最后一个节点指向0，方便处理
		ptr = head;
		i = 0;
		while(ptr){
			node_vec[i]->next = node_vec[i+1]; // 连接链表 
			if (ptr->random) {
				int id  = node_map[ptr->random];
				node_vec[i]->random = node_vec[id]; // 拷贝原链表的random指针 
			}
			ptr = ptr->next;
			i++; 
		} 
		return node_vec[0];
	}
};

排序链表

每个链表都有序，合并后仍然有序

#include<stdio.h>

struct list{
	int val;
	list *next;
	list(int x): val(x), next(NULL);
}; 

class Solution{
public:
	list *mergeTwoLists(list *l1, list *l2){
		list temp_head(0);
		list *pre = &temp_head;
		while (l1 && l2){ // 排序操作 
			if(l1->val < l2->val){
				pre->next = l1;
				l1 = l1->next;
			}
			else{
				pre->next = l2;
				l2 = l2->next;
			}
			pre = pre->next;
		}
		if(l1){ // 如果l1还有剩余 
			pre->next = l1;
		}
		if(l2){ // 如果l2还有剩余 
			pre->next = l2;
		}
		return temp_head.next; // 返回排序后的头指针 
	}
};

多个排序链表的合并

思路一：两个合为一个，再和第三个合

TLE

思路二：全部存入vector排序，后连接

O(KNlogKN + KN)

// 全部放入vector，排序后连接

bool cmp(const list *a, const list *b) {
	return a->val < b->val;
}

class Solution{
public:
	list* mergeKlist(std::vector<list*> & lists) { // 传引用，lists是一个存着每个链表头指针的vector 
		std::vector<list*> node_vec;
		for (int i = 0; i < lists.size(); i++) {
			list *head = lists[i];
			while(head){ // 遍历k个链表，将节点全部添加至node_vec 
				node_vec.push_back(head);
				head = head->next;
			}
			if(node_vec.size() == 0) return NULL;
			std::sort(node_vec.begin(), node_vec.end(), cmp); // 排序 
			for(int i = 1; i < node_vec.size(); i++){
				node_vec[i-1]->next = node_vec[i];
			}
			node_vec[node_vec.size()-1]->next = NULL; // 尾节点指向空 
			return node_vec[0]; // 返回新得长链表得头指针 
		} 
		
	}
}; 

思路三： 分治，两两合并

O（KNlogK）

list *mergeTwoLists(list *l1, list *l2){
	list temp_head(0);
	list *pre = &temp_head;
	while (l1 && l2){ // 排序操作 
		if(l1->val < l2->val){
			pre->next = l1;
			l1 = l1->next;
		}
		else{
			pre->next = l2;
			l2 = l2->next;
		}
		pre = pre->next;
	}
	if(l1){ // 如果l1还有剩余 
		pre->next = l1;
	}
	if(l2){ // 如果l2还有剩余 
		pre->next = l2;
	}
	return temp_head.next; // 返回排序后的头指针 
}

list* mergeKLists(std::vector<list*> &lists) {
	if(lists.size() == 0) return NULL;
	if(lists.size() == 1) return lists[0];
	int mid = lists.size()/2;
	std::vector<list*> sub1;
	std::vector<list*> sub2;
	for (int i = 0; i < mid; i++) sub1.push_back(lists[i]);
	for (int i = mid; i < lists.size(); i++) sub2.push_back(lists[i]);
	list *l1 = mergeKLists(sub1);
	list *l2 = mergeKLists(sub2);
	return mergeTwoLists(l1, l2);//分治处理 
}