【算法C++实现】4、链表（包括哈希表、顺序表的简单介绍）

发布时间：2024-01-16 05:01:35

文章目录

1 链表相关容器介绍

1.1 哈希表

暂时只用于刷题辅助用，不要求掌握内部结构

C++中是STL的std::unordered_map。
关联容器，存储了键-值对，并通过哈希函数对键进行散列来实现快速的增删改查，平均情况下具有常数时间复杂度 O ( 1 ) O(1) O(1)，但时间复杂度还是比数组随机访问要高得多。

几个重点

  • 使用哈希表，可简单的理解为它是一种无序的集合结构，key值不能重复

  • 键-值对，用std::unordered_map

    • 增:[ ], insert(make_pair(key, value)), emplace(key, value)
    • 删:erase(key)，clear()
    • 改:[ ]
    • 查:find(key), count(key)
      #include <unordered_map>  
#include <string>
#include <iostream>
int main() {
	std::unordered_map<std::string, int> hashMap;
    // 增
    hashMap["apple"] = 5;	
    hashMap.insert(std::make_pair("banana", 3));
    hashMap.emplace("orange", 4); 	// C++11特性，原位构建
    // 删
    hashMap.erase("banana"); // hashMap.clear()清空
    // 改
    hashMap["apple"] = 4	
    // 查
    if (hashMap.find("apple") != hashMap.end())
    	std::cout << "键apple存在" << std::endl;
    if (hashMap.count("orange") > 0)	// 1则有，0则无
    	std::cout << "键orange存在" << std::endl;

	return 0;
}

  • 如果只有键，没有值，用std::unordered_set

    • 增:insert(key), emplace(key)
    • 删:erase(key)，clear()
    • 改:没有改操作
    • 查:find(key), count(key)
      #include <unordered_set>
#include <string>
#include <iostream>
int main() {
	std::unordered_set<string> hashSet;
	// 增
	hashSet.insert("apple");
	hashSet.emplace("banana");
	// 删
	hashSet.erease("banana");
	// 查
	if (hashSet.find("apple") != hasSet.end())
		std::cout << "有apple" << std::endl;
	if (hashSet.count("apple") > 0)
		std::cout << "有apple" << std::endl;
	return 0;
}

  • 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用为这个值所需空间大小

  • 放入哈希表的东西，如果是自定义类型，内部按引用传递，内存占用为指针所需大小

1.2 有序表的简单使用

  • 使用有序表，可简单将其理解为一种有序的集合结构，key值不能重复

  • 单键用std::set；键-值对用std::map。增删改查API跟哈希相同

  • 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同

  • 基础类型：值传递。自定义类型：引用传递

  • 不管什么底层实现，只要是有序表。固定时间复杂度 O ( l o g N ) O(logN) O(logN)

  • 只要是有序表，都有固定功能：

    • insert(key, value) or emplace(key, value)将一条记录加入表中，或者将key的记录更新成value
    • erase()删除一条记录
    • begin()获取key最小的一条记录
    • lower_bound()获取顺序表中>=给定key值的第一条记录的迭代器
    • upper_bound()获取顺序表中>给定key值的第一条记录的迭代器
    • find()获取指定key值的记录的迭代器，如果不等于end()则有效
    • at()获取指定key值对应的值，会进行边界检查，如过形参超过边界，抛出std::out_of_range类型异常
    #include <string>
#include <iostream>
#include <map>
void main(){
	std::map<int,string> myMap;
	for (int i = 0; i < 10; i++){
		myMap.insert(std::pair(i, "我是" + i);
	}
 	string str = myMap.begin()->first;	// 获取key值最小的记录(std::pair类型)
 	myMap.erase(2);	// 删除key为2的记录
 	auto it = myMap.lower_bound(8); // key>=8的第一个记录的迭代器
 	auto it = myMap.upper_bound(8); // key>8的第一个记录的迭代器
 	auto it = myMap.--upper_bound(8); // <=8的最后一个元素，即>8的第一个元素的前一个位置，注意这里千万不能后自减，因为返回值是临时变量
	
	// 使用find() 查找指定的键，因为2已经删除了，会找不到
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Record found: Key = " << it->first << ", Value = " << it->second << std::endl;
    } else {
        std::cout << "Record not found." << std::endl;
    }
    // 使用at()获取指定key的对应的值
    try {
        int value = myMap.at(key);
        std::cout << "Record found: Key = " << key << ", Value = " << value << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "Record not found." << std::endl;
    }
	
}

  • 如果顺序表存放自定义类型，因为需要排序，所以需要在类中重载 < 操作符。根据文档要求，该运算符重载函数必须是常函数并且形参用const修饰。也可以在创建map对象时直接传入一个用于比较的函数的指针

    	#include <iostream>
	#include <map>
	#include <string>
	class Person {
	public:
	    Person(const std::string& n, int a) : name(n), age(a) {}
	    std::string name;
	    int age;
	    // 重载<运算符，注意常函数和常形参
	    bool operator<(const Person& other) const {
	        return age < other.age;
	    }
	};
	
	// 自定义类型比较方式（通过函数对象，也可以通过普通函数）
	struct CompareByName {
	    bool operator()(const Person& p1, const Person& p2) const {
	        return p1.name < p2.name;
	    }
	};
	
	int main() {
	    std::map<Person, int> ageMap;
	    std::map<Person, int, CompareByName> nameMap;	// 注意在<>里面，类型名后面不要带()，如果是std::find_if()这种操作，在传入谓词时函数对象时，则该对象需要带()
	    Person p1("Alice", 25);
	    Person p2("Bob", 30);
	    // 使用默认的比较函数（按照年龄排序）
	    ageMap[p1] = 25;
	    ageMap[p2] = 30;
	    // 使用自定义的比较函数（按照姓名排序）
	    nameMap[p1] = 25;
	    nameMap[p2] = 30;
	    for (const auto& entry : ageMap) {
	        std::cout << "Age: " << entry.first.age << ", Value: " << entry.second << std::endl;
	    }
	    for (const auto& entry : nameMap) {
	        std::cout << "Name: " << entry.first.name << ", Value: " << entry.second << std::endl;
	    }
	    return 0;
	}
	```

试了一下在VS2022中，有下面这种规则，应该是函数对象作谓词如果放在<>中，不加括号，如果放在()中，则需要带()
std::find_if(it1, it2, IsOdd()); // 这里如果IsOdd是个类，内部重载了()运算符，必须加括号
std::map<Person, int, CompareByName> nameMap; // 不能加括号

2 链表的一些简单题

2.1 题：单向链表反转

leetcode 206 简单

#include <iostream>
class ListNode {
public:
	ListNode(int x) : val(x), next(nullptr) {}	
	int val;
	ListNode* next;
};
ListNode* reverseList(ListNode* pHead) {
	ListNode* pPrev = nullptr;
	ListNode* pNext = nullptr;
	while (pHead != nullptr) {	// pHead即为当前节点
		// 先断后连原则
		pNext = pHead->next;// 断：断之前保存下个节点的指针（否则下个节点就丢失了）
		pHead->next = pPrev;// 连：next连到新的节点上（上一个节点）
		
		// 更新当前节点，更新之前保存上一个节点的地址（否则上个节点就丢失了）
		pPrev = pHead;
		pHead = pNext;
	}
	return pPrev;
}
void printList(ListNode* pHead) {
	ListNode* curNode = pHead;
	while (curNode != nullptr){
		std::cout << curNode->val << " -> ";
		curNode = curNode->next;
	}
	std::cout << "nullptr" << std::endl;
}
int main()
{
	ListNode* pHead = nullptr;
	ListNode* pTail = nullptr;
	for (int i = 1; i < 11; i++) {
		if (!pHead) {
			pHead = new ListNode(i);
			pTail = pHead;
		}
		else {
			pTail->next = new ListNode(i);
			pTail = pTail->next;
		}
	}
	std::cout << "原始链表：";
	printList(pHead);

	pHead = reverseList(pHead);

	std::cout << "反转后的链表：";
	printList(pHead);

	// 释放堆区空间
	ListNode* p;
	while (pReversedHead){
		p = pReversedHead;
		pReversedHead = pReversedHead->next;
		delete p;
	}

	std::cin.get();
	return 0;
}

2.2 题：双向链表反转

ListNode* reverseDoubleList(ListNode* pHead) {
	ListNode* pPrev = nullptr;
	ListNode* pNext = nullptr;
	while (pHead)
	{
		// 交换节点的next prev指针变量。先断后连，断前先暂存
		pNext = pHead->next;	 
		pHead->next = pHead->prev; 
		pHead->prev = pNext;
		// 必须有pPrev这个临时变量用来存放前一个节点的地址，因为循环结束后
		// pHead和pNext都为nullptr，如果不存放前一个节点地址，我们就找不到最后一个节点的地址了
		pPrev = pHead; 
		pHead = pNext;
	}
	
	return pPrev;
}
int main()
{
	ListNode* pHead = nullptr;
	ListNode* p = nullptr;
	for (int i = 1; i <= 10; i++){// 构造双向链表
		if (!pHead){
			pHead = new ListNode(i);
			p = pHead;
		}
		else{
			p->next = new ListNode(i);
			p->next->prev = p;
			p = p->next;
		}
	}
	// 翻转操作...
	// 打印输出...
	// 释放空间...
}

2.3 题：打印两个有序链表的公共部分

【题目】给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
【要求】若果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复杂度为O(1)
思路：两个指针，谁小谁移动，相等就打印，直到某一个指针越界为止

#include<iostream>
class Node {
public:
	Node(int a) : val(a), next(nullptr) {}
	int val;
	node* next;
};

void printCommonPart(Node* head1, Node* head2) {
	while (head1 && head2) {
		if (head1->val < head2->val) {
			head1 = head1->next;
		}
		else if (head1->val > head2->val) {
			head2 = head2->next;
		}
		else {
			std::cout << head1->val << " ";
			head1 = head1->next;
			head2 = head2->next;
		}
	}
}

int main()
{
	Node* head1 = new Node(1);
	Node* p1 = head1;
	for (int i = 2; i <= 10; i++) {
		p1->next = new node(i);
		p1 = p1->next;
	}
	Node* head2 = new Node(2);
	head2->next = new Node(4);
	head2->next->next = new Node(6);
	
	printCommonPart(head1, head2);
	
	std::cin.get();
	return 0;
}

3 面试链表题型方法论

（1）笔试，不用太在意空间复杂度，一切为了时间复杂度。说白了就是为了进面，只要满足时间复杂度并通过就行了。切忌花费大量时间抠一些怪、难方法。
（2）面试，时间复杂度依然在第一位，但一定要找到空间最省的方法（靠这个提升竞争力）

链表题型重要技巧：

  • 额外数据结构记录（数组、哈希表等容器）
  • 快慢指针

4 题：判断一个链表是否是回文结构

leetcode 234 简单

【题目】给定一个单链表的头结点head，请判断该链表是否为回文结构
【例子】1->2->1，返回true；1->2->2->1，返回true；1->2->3，返回false。
【要求】如果链表长度为N，时间复杂度要求O(N)，空间复杂度O(1)。

笔试做法（空间复杂度O(N)）：搞个栈，遍历链表，全部压入栈内，然后出栈的顺序就是逆序了，挨个与链表每个节点比较，全等则是回文。

#include <stack>
class Node {
public:
	Node(int x) : val(x), next(nullptr) {}
	int val;
	Node* next;
};
// 用额外N空间，判断是否回文
bool isPalindrome1(Node* head) {
	if (!head || !head->next) {
		return true;
	}
	std::stack<Node*> myStack;
	Node* p = head;
	// 把链表所有节点压入栈
	while (p) {
		myStack.push(p);
		p = p->next;
	}

	// 出栈同时，判断是否相等
	while (head) {
		if (head->val != myStack.top()->val) {
			return false;
		}
		head = head->next;
	}
	return true;
}

稍微优化它的空间复杂度的做法：让链表的后面一半元素入栈，空间复杂度降低到O(N/2)，如何实现？—— 快慢指针

4,1 快慢指针介绍

快指针走2步，慢指针走1步，当快指针走到尾节点，慢指针刚好走一半

快慢指针一定要自己写代码，熟练以下几种控制慢指针位置的边界情况。当快指针走完时

  • 如果链表节点为奇数个，慢指针在中点、中点的前一个位置、中点的后一个位置
  • 如果偶数个，慢指针在中间分界线的前一个位置、前两个位置、后一个位置

熟练是为了在笔试或面试的时候节省时间

快指针可以继续往后走的条件（经过大量实践总结出来的，最好的写法）
fast->next != nullptr && fast->next->next != nullptr
最终快指针必然停在尾结点(奇数个) 或 尾结点前一个节点（偶数个）。

根据fast指针位置，可以判断链表结点个数奇偶性

  • 奇数：fast->next == nullptr
  • 偶数：fast->next != nullptr && fast->next->next == nullptr

根据奇偶性，可以知道慢指针的精确位置

  • 如果是奇数个节点，在正中间N/2+1
  • 如果是偶数个节点，在中分线前一个位置N/2

拿到慢指针精确位置，就可以拿到其相邻的节点位置

  • 后一个：slow->next，后两个：slow->next-next

  • 前一个：额外申请一个指针prev，在慢指针往后走之前，记录slow的指向

    while (fast->next != nullptr && fast->next->next != nullptr) {
	Node* prev = slow;
	fast = fast->next->next;
	slow = slow->next;
}

/ 是整除

4.2 题：判断回文结构（额外空间优化成O(N/2)）

利用快慢指针找到中点，只把链表的后半部分入栈，然后出栈并与链表前部分一一比对

bool isPalindrome2(Node* head) {
	if (!head || !head->next) {
		return true;
	}
	Node* right = head->next;	// 慢指针
	Node* cur = head;			// 快指针
	// 找到链表的右半部分的起始指针
	while (cur->next && cur->next->next) {
		right = head->next;
		cur = cur->next->next;
	}

	// 入栈
	std::stack<Node*> stack;
	while (right) {
		stack.push(right);
		right = right->next;
	}
	
	// 出栈
	while (!stack.empty()) {
	    cur ＝ stack.top();
	    stack.pop();
		if (head->val != cur->val)
			return false;
		head = head->next;
	}
	return true;
}

4.3 题：判断回文结构（额外空间O(1)）

这种才是面试应该回答的内容，考察coding能力

再次强调，笔试直接用栈嘎嘎快

步骤：

  • 快慢指针找到中点，把中点next指针指向nullptr
  • 从中点下一个节点开始反转链表
  • 然后用head指针从前往后，用fast指针从后往前遍历，判断每个数是否相等，直到有一个指针为空。（不管是奇数个偶数个都一样）
bool isPalindrome3(Node* head) {
	if (!head || !head->next) {
		return true;
	}
	// 找中点
	Node* fast = head;
	Node* slow = head;
	while (fast->next && fast->next->next) {
		fast = fast->next->next;
		slow = slow->next;
	}
	// 反转中点往后的链表，需要3个指针，复用一下slow 和fast
	Node* cur = slow->next;	// 后半部分的第一个节点
	slow->next = nullptr;
	while (cur) {
		fast = cur->next;
		cur->next = slow;	
		slow = cur;
		cur = fast;
	}
	cur = slow; // 暂存尾结点,用于复原
	// 然后开始逐一判断，是否是回文结构
	bool res = true;
	fast = head;
	while (slow && fast) {
		if (fast->val != slow->val){
			res = false;
			break;
		}
		fast = fast->next;
		slow = slow->next;
	}
	// 最终还要把链表恢复原样(目前cur指向尾结点）
	slow = cur->next; // 尾结点的前一个节点
	cur->next = nullptr; // 尾结点next恢复成空
	while (slow) {
		fast = slow->next;
		slow->next = cur;
		cur = slow;
		slow = fast;
	}
	return res;
}

5 题：将单链表按某值划分为左边小、中间相等、右边大的形式

leetcode 86 中等

【题目】给定一个单链表的头结点head，节点的值类型是int，再给定一个整数pivot。实现一个调整链表的函数，将其调整为左部分都是小于pivot的节点，中间部分等于，右边小于

【进阶】增加要求

  • 调整后，所有节点的相对顺序和调整前一样
  • 时间复杂度达到O(N)，空间复杂度达到O(1)

5.1 借助数组（笔试做法）

搞个指针数组，把所有节点的地址放进去，对这些指针做个patition，最后重新串成一个链表返回即可
空间复杂度O(N)，不稳定

#include <algorithm> // std::swap
Node* listPartition1(Node* head, int pivot) {
	if (!head) return head;
	
	// 指针数组创建
	Node* cur = head;
	std::vector<Node*> nodeArr;
	while (cur) {
		nodeArr.push_back(cur);
		cur = cur.next;
	}

	// 指针数组patition操作
	int small = -1;
	int big = nodeArr.size();
	int index = 0;
	while (index != big) {
		if (nodeArr[index]->value < pivot) { // 如果小，数组首位开始交换
			std::swap(nodeArr[++small], nodeArr[index++]);
		} else if (nodeArr[index]->value == pivot) {
			index++;
		} else {// 当前值大于pivot，数组末位开始交换，注意index不++因为换过来的数大小未知
			std::swap(nodeArr[--big], nodeArr[index]);
		}
	}
	
	// 重连链表
	for (int i = 0; i != nodeArr.size(); i++) {
		nodeArr[i - 1]->next = nodeArr[i];
	} 
	nodeArr[i - 1]->next = nullptr;
	
	return nodeArr[0];
}

5.2 仅借助6个额外指针（面试做法）

视频地址

要求： 额外空间复杂度O(1)

办法： 用6个额外变量，分别用于表示三个区间的头、尾节点地址

过程： 扫描一遍链表，用当前结点的值与target相比，小的就用小指针穿起来，相等的就用相等的指针穿起来，同理大的也一样。以小的为例，第一次遇到一个小值，则头尾指针都指向它 ，因为目前小区间内就它一个节点。直到遇到第二个小于target的数，把尾指针指向该节点，并把之前区间的最后一个结点的next指针指向它。后续以及其他区间的操作都是一样的。最后利用六个额外指针的信息，把三个区间依次连成一个链表即可。

利用了链表的插入灵活性

Node* listPartition2(Node head, int pivot) {
	Node* sH = nullptr;
	Node* sT = nullptr;
	Node* eH = nullptr;
	Node* eT = nullptr;
	Node* lH = nullptr;
	Node* lT = nullptr;
	Node next = nullptr;
	// 所有结点分到三个新链表中去
	while (head) {
		// 先断
		next = head.next;	
		head.next = nullptr;	
		if (head.value < pivot) {
			if (sH == nullptr) {
				sH = head;
				sT = head;
			} else {
				sT.next = head;
				sT = head;
			}
		} else if (head.value == pivot) {
			if (eH == nullptr) {
				eH = head;
				eT = head;
			} else {
				eT.next = head;
				eT = head;
			}
		} else {
			if (lH == nullptr) {
				lH = head;
				lT = head;
			} else {
				lT.next = head;
				lT = head;
			}
		}
		head = next;
	}
	// 重连3个链表（精简版本）
	if (sT) {	// 如果有小于区域
		sT.next = eH;	// 不管有没有等于区域，都这么写，没有就是置空
		eT = eT == nullptr ? sT : eT;	// 判断是否有等于区域，用eT记录谁去连大于区域
	}
	// 用eT指向的节点的next指针连大于区域（大于区域有没有无所谓，没有就是nullptr）
	if (eT != nullptr) { 
		eT.next = lH;
	}

	return sH != nullptr ? sH : (eH != nullptr ? eH : mH);
}

6 复制含有随机指针的链表

leetcode 138 中等

【题目】一种特殊的单链表节点类描述如下

class Node {
	int value;
	Node* next;
	Node* rand;
	Node(int val) {
		value = val;
	}
};

rand指针式单链表节点结构中新增的指针，可能指向链表中任意一个节点，也可能指向null。给定一个无环单链表的头结点head，实现一个函数完成链表复制，并返回新链表的头结点。
【要求】时间复杂度O(N)，额外空间复杂度O(1)

想想如何实现，正常复制一个链表，只需要一个循环每次用上个节点的next指针指向一个new出来的结点，拷贝结点内容即可。如果内容中有随机指针，就不好搞了，因为要复制这个随机指针指向的内容比较麻烦，比如：每次循环用上一个节点的rand->next = new Node(原本结点rand指针指向的那个结点的val值)，这样做如果存在1个以上的rand指针指向该节点，则会new两个地址不同的结点出来，从而得到错误的结构。因此，这个题还挺麻烦的吧，为了不重复new出同样内容的结点，可以用哈希表解决，虽然引入了O(N)的空间复杂度

6.1 借用哈希表

借助std::unordered_map

  • key：老结点
  • value：依照老结点的内容，新new出来的结点

这样就能通过老结点的rand指针，查到它指向的结点，并通过map找到我们new出来的新结点，不会产生重复new结点的问题

#include <unordered_map>
Node* copyListWithRand1(Node* head) {
	if (!head) return nullptr;
	// 把新旧结点放入哈希表中
	std::unordered_map<Node*, Node*> map;
	Node cur = head;
	while (cur) {
		map.emplace(cur, new Node(cur->val));
		cur = cur->next;
	}
	
	// 
	cur = head;
	while (cur) {
		map[cur]->next = map[cur->next];
		map[cur]->rand = map[cur->rand];
		cur = cur->next;
	}
	return map[head];
}

6.2 不用哈希表

秀的不行，把新结点插入到与之对应的老结点的后面，这样在复制链表的时候，只需要把新结点的rand指向老结点的rand->next就行，同理新结点的next指向老结点的next->next。

Node* copyListWithRand1(Node* head) {
	if (!head) return nullptr;
	// 插入新结点
	Node* cur = head;
	Node* next = nullptr;
	while (cur) {
		next = cur->next;
		cur->next = new Node(cur->val);
		cur->next->next = next;
		cur = next;
	}
	// 处理新结点的rand指针
	cur = head;
	Node* curCopy = nullptr;
	while (cur) {
		next = cur->next->next;	// 原链表的原本的下一个节点
		curCopy = cur->next;
		curCopy->rand = cur->rand ? cur->rand->next : nullptr;
		cur = next;
	}
	// 分离(处理next指针)
	Node res = head->next;
	cur = head;
	while (cur) {
		next = cur->next->next;
		curCopy = cur->next;
		cur->next = next;
		curCopy->next = next ? next->next : nullptr;
		cur = next;
	}
	return res;
}

7 两个单链表相交的问题(单链表最难的算法题）

【题目】给定两个可能有环单链表，头结点head1和head2。请实现一个函数，如果两个链表相交，返回相交的第一个节点。如果不想交，返回null。
【要求】如果两个链表长度之和为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

重点：单链表只有一个next指针

思路可以分为以下几个步骤：

  • 判断两个链表是否有环，如果有环的话，找到两个链表各自的入环点：
    • 快慢指针。具体方法是，分别用一个快指针和一个慢指针遍历链表，如果指针遇到null，则链表无环；如果两个指针相遇，则链表有环。
    • 如果链表有环，快指针放到头结点，与慢指针同时从各自位置继续遍历链表（每次都前进1步），直到再次相遇，此时的节点就是入环点。

      快慢指针有环必定相遇还好。找头结点这个没啥办法，正常人谁能想到？
      这种题，做过就会，没做过就噶了

  • 判断是否相交：
    • 如果两个链表都无环，说明它们是Y型相交（只有一个next指针，相交后，两条链表的后面所有结点必然重合），可以直接按照无环链表相交的方法查找相交节点。
    • 如果其中一个链表有环而另一个链表无环，则它们不可能相交（因为每个节点只有一个next指针）。
    • 如果两个链表都有环，则可能是三种情况：
      • 不相交
      • 相同入环点，同一个环
      • 不同入环点，同一个环
  • 返回相交的节点：如果两个链表有交点，返回交点的第一个节点。如果不相交，则返回null。

下面逐步骤设计函数

(1) 判断链表是否有环，如果有环的话，找到入环点

Node* getLoopNode1(Node* head) {
	if (!head || !head->next || !head->next->next)
		return nullptr;
	Node* n1 = head->next; 		// slow
	Node* n2 = head->next->next;// fast
	// 只要没相遇就一直循环
	while (n1 != n2) {	
		if (!n2->next || !n2->next->next) { // 走到链尾了 return
			return nullptr;
		}
		n2 = n2->next->next;
		n1 = n1->next;
	}
	// 没走到链尾，且退出循环了 说明相遇了。 找入环结点
	n2 = head;
	while (n1 != n2) {
		n1 = n1->next;
		n2 = n2->next;
	}
	return n1;
}

题目不要求时间复杂度的话，借用哈希表更简单

(2) 都无环，Y型相交

这里还是保留自己的垃圾写法吧，左哥的写法更美丽，在都有环且入环点相同的情况中可以看到。

Node* noLoop(Node* head1, Node* head2) {
	if (!head1 || !head2) return nullptr;
	
	Node* n1 = head1;
	Node* n2 = head2;
	int len1 = len2 = 0;
	while (n1->next) {
		len1++;
		n1 = n1->next;
	}
	while (n2->next) {
		len2++;
		n2 = n2->next;
	}
	if (n1 != n2)
		return nullptr;
	// 较长的那个前进到与较短链表相同长度，然后一起往后走，直到遇到第一个共同结点
	int sub = 0;
	if (len1 > len2) {
		sub = len1 - len2;
		n1 = head1;		// n1指向较长的链表的头
		n2 = head2;
	} else {
		sub = len2 - len1;
		n1 = head2;		// n1指向较长的链表的头
		n2 = head1;
	} 
	while (sub != 0) {	// 较长的前进
		n1 = n1->next;
		sub--;
	}
	while (n1 != n2) {	// 一起前进
		n1 = n1->next;
		n2 = n2->next;
	}
	return n1;
}

(3) 都有环

三种情况如图所示
三种情况

#include <iostream>
#include <cmath>
Node* bothLoop(Node* head1, Node* loopIn1, Node* head2, Node* loopIn2) {
	if (!head1 || !head2) return nullptr;

	Node* n1 = nullptr;
	Node* n2 = nullptr;
	// 情况1：相同入环点，与Y型相交一样
	if (loopIn1 == loopIn2) {
		n1 = head1;
		n2 = head2;
		int num = 0;	// 两个链表到入环点所走的步数之差
		while (n1 != loopIn1) {	// 注意这里是走到入圈点结束
			num++;
			n1 = n1->next;
		}
		while (n2 != loopIn2) {
			num--;
			n2 = n2->next;
		}
		n1 = num > 0 ? head1 : head2;
		n2 = n1 == head1 ? head2 : head1;
		num = std::abs(num);
		
		// 长的先走num步
		while (num != 0) {
			num--;
			n1 = n1->next;
		}

		// 一起走到第一个相交点
		while (n1 != n2) {
			n1 = n1->next;
			n2 = n2->next;
		}
		return n1;
	} else {	
		// 情况2：入环点不同，很简单n1在环里走一圈，如果相交，则n1会碰到loopIn2
		n1 = loopIn1->next;
		while (n1 != loopIn2) {
			if (n1 == loopIn2) {
				return n1;
			}
			n1 = n1->next;
		}
	}
	
	return nullptr; // 情况3：都有环但不相交
	
}
文章来源:https://blog.csdn.net/Motarookie/article/details/131867094
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章