C++数据结构与算法_线性表_链表
文章目录
本文记录链表的概念、链表实现、链表优缺点并刷leetcode上的练习题。
第二章 线性表
2.2 链表
链表解决了数组在内存中不能连续存放的问题。
链表的时间复杂度：查找O(n); 删除，插入（头插或尾插）是O(1)；
2.2.1 实现一个链表
实现一个链表，支持头插入，尾查，查找元素，删除元素，删除所有value的元素，打印链表。
// 支持头插入，尾查，查找元素，删除元素，删除所有value的元素，反转链表，打印链表classLinkList{public:LinkList():m_pHead(newNode(-1)),m_pTailNode(m_pHead){}~LinkList(){// 释放所有链表 Node* p = m_pHead->next;while(p !=nullptr){ Node * tmp = p; p = p->next;delete tmp;}delete m_pHead; m_pHead =nullptr;}// 头插入voidinsertHead(int data){ Node* tmp =newNode(data); tmp->next = m_pHead->next; m_pHead->next = tmp;// 更新尾部节点if(m_pHead == m_pTailNode){ m_pTailNode = tmp;}}// 尾部插入voidinsertTail(int data){ Node* tmp =newNode(data); m_pTailNode->next = tmp; m_pTailNode = tmp;}// 查找boolfind(int data){// 遍历链表 Node* firstdata = m_pHead->next;while(firstdata !=nullptr){if(firstdata->data == data){returntrue;} firstdata = firstdata->next;}returnfalse;}// 删除第一个元素voiddeleteNode(int data){ Node* firstdata = m_pHead->next; Node* tmp = m_pHead;while(firstdata !=nullptr){if(firstdata->data == data){ tmp->next = firstdata->next;return;} tmp = firstdata;// 记录上一个节点 firstdata = firstdata->next;}}// 删除所有的value节点voiddeleteNodeAll(int data){ Node* firstdata = m_pHead->next; Node* tmp = m_pHead;while(firstdata !=nullptr){if(firstdata->data == data){ tmp->next = firstdata->next;}else{ tmp = firstdata;// 记录上一个节点} firstdata = firstdata->next;}}// 遍历链表voidprintNode(){ Node* p = m_pHead->next;while(p)// p指向最后一个节点的后继节点，nullptr{ cout << p->data <<" "; p = p->next;} cout << endl;}private:// int节点和Node指针structNode{Node(int da =0):data(da),next(nullptr){}int data; Node* next;}; Node* m_pHead; Node* m_pTailNode;// 添加一个节点避免每次尾插时都是遍历一遍};voidtest(){ LinkList list; list.insertHead(1); list.insertHead(2); list.insertHead(3); list.insertHead(3); std::cout << list.find(4)<< std::endl; std::cout << list.find(3)<< std::endl; list.insertTail(4); list.insertTail(5); list.insertTail(6);// 删除一个 元素 list.deleteNodeAll(3); list.printNode();}结果：
01214562.2.2 链表优缺点
优点：
内存利用：内存利用率高，不需要大块连续内存。
插入和删除：插入和删除节点不需要移动其他节点，时间复杂度O(1)；
扩容：不需要专门进行扩容操作。
缺点：
内存占用量大，每个节点除了保存数据之后，还要保存一个指针。假如数组中存放100w个整型，内存是400w byte; 如果用链表实现：100w*8=800w byte
访问：节点不连续，无法进行随机访问。
**随机访问多：**用数组，O(1)；
**增加删除多：**用链表 O(1)；
2.2.3 链表刷题
2.2.3.1 反转链表（单链表逆序）
对应了leetcode 206
https://leetcode.cn/problems/reverse-linked-list/description/
题目描述：
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
解题思路：将逆序和头插联系起来。力扣上是个无头链表，需要new一个头部，并且置空，然后将原来的链表通过头插入链表内。
p->next = head->next; head->next=p; p = q;ListNode*reverseList(ListNode* head){ ListNode *newHead =newListNode(-1,nullptr); ListNode *currentNode = head;while(currentNode !=nullptr){// 记录下一个节点 ListNode *tmp = currentNode->next;// 头插 currentNode->next = newHead->next; newHead->next = currentNode; currentNode = tmp;} std::unique_ptr<ListNode>ptr(newHead);return newHead->next;}2.2.3.2 删除链表倒数第n个节点 19
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
这个链表是一个无头链表。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
思路：采用双指针方式，p和q同时指向Head, 假如求倒数第3个节点，p向前移动3个节点，然后p q 同时移动，当p->next等于空时候，q指向的就是倒数第k个节点的前一个节点，然后直接q->next = q->next->next即可；
ListNode*removeNthFromEnd(ListNode* head,int n){// 这道题，可以不使用dummy，因为相对位置不变。 ListNode *pslow = head; ListNode *pfast = head;// p先走n + 1步，指向删除的前一个for(int i =0;i < n;++i){ pfast = pfast->next;}// 两个一起走, 知道pfast走到最后一个节点while(pfast->next !=nullptr){ pfast = pfast->next; pslow = pslow->next;}// 此时slow指向了删除的前一个节点 pslow->next = pslow->next->next;return head;}2.2.3.3 合并两个有序单链表 21
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
解题思路：使用双指针思想。对于无头链表，先判断哪个链表的头结点最小；然后按照顺序插入到最小的链表中。当一个链表插入完毕后，将其他直接插入进来即可。
先申请一个节点作为合并之后的节点的头部。使用两个指针p和q 分别指向link1和link2，遍历来比较这两个链表，将较小的元素插入到新的头部。最后，哪个不为空，newLinkCurrent->next = (p == nullptr ? q : p);
ListNode*mergeTwoLists(ListNode* list1, ListNode* list2){// 指向待插入的位置if(list1 ==nullptr&& list2 ==nullptr){returnnullptr;}if(list1 ==nullptr){return list2;}if(list2 ==nullptr){return list1;} ListNode *phead =nullptr;if(list1->val < list2->val){ phead = list1; list1 = list1->next;}else{ phead = list2; list2 = list2->next;} phead->next =nullptr; ListNode *ptail = phead;while(list1 !=nullptr&& list2 !=nullptr){if(list1->val < list2->val){ ptail->next = list1; ptail = list1; list1 = list1->next;}else{ ptail->next = list2; ptail = list2; list2 = list2->next;}}// 看哪个链表提前为空// if (list1 != nullptr)// {// ptail->next = list1;// }// else if (list2 != nullptr)// {// ptail->next = list2;// }// 使用三目运算符实现 ptail->next =(list1 !=nullptr)? list1 : list2;return phead;}2.2.3.4 环形链表II
题目描述：
给定一个链表的头节点head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
解题思路：使用两个指针，快指针和慢指针，分别从头节点出发，快指针每次走两个格子，慢指针每次走一个格子，如果两个指针在途中相遇，说明这个链表有环。
为什么快指针一定遇上慢指针？
相对于慢指针，快指针比慢指针只多一个节点，这就相当于慢指针不移动，快指针每次走一个节点，所以快指针一定会遇到慢指针。
快慢指针相遇时走过的总节点计算.
假设从头结点到环形入口节点的节点数为x；环形入口节点到 fast指针与slow指针相遇节点时的节点数量为y。从相遇节点再到环形入口节点数为 z。
fast走过的路径为：fast至少走过一圈，fast一定是追赶慢指针。
x + y + z + y
slow走过的路径为：
x + y
列出等式：因为快指针每次走两步，慢指针每次走一步，所以快指针走过的路程是慢指针的两倍。
(x + y + z + y) = 2 * (x + y)
x + z = 2 * x
x = z
最后得到 x = z ; 说明从相遇节点再次到环的入口距离与从头结点到环的入口距离相同。
ListNode *detectCycle(ListNode *head){// x = z ListNode *slow = head; ListNode *fast = head;while(fast !=nullptr&& fast->next !=nullptr){ fast = fast->next->next;// 快指针每次走两个格子 slow = slow->next;// 慢指针每次走一个格子if(slow == fast)// 相遇节点{// 相遇后，慢指针从头开始走，每次走一个格子// 快指针从相遇位置走，每次走一个格子 slow = head;while(fast != slow){ fast = fast->next; slow = slow->next;}return fast;}}returnnullptr;}上面代码中：while (fast != nullptr && fast->next_ != nullptr) 这样判断目的？
fast 不为空，这样才能访问 fast->next
fast->next 不为空，这样才能访问 fast->next->next
2.2.3.6 求两个链表相交节点 160
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构。
解题思路：两个指针分别指向两个链表，分别走完后，记录下各个链表长度；len1 - len2 = diff;
长链表先走diff个元素，然后两个链表一起走，每次走一步都要判断是否等；
相等就是两个链表的交点
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){/* 解题思路：两个指针分别指向两个链表，分别走完后，记录下各个链表长度；len1 - len2 = diff; 长链表先走diff个元素，然后两个链表一起走，每次走一步都要判断是否等； 相等就是两个链表的交点 */// 记录len1和len2长度 ListNode *pa = headA; ListNode *pb = headB;int len1 =0;int len2 =0;while(pa !=nullptr){ len1++; pa = pa->next;}while(pb !=nullptr){ len2++; pb = pb->next;} pa = headA; pb = headB;int diff;if(len1 > len2){ diff = len1 - len2;// A先走dif步for(int i =0;i < diff;++i){ pa = pa->next;}}else{ diff = len2 - len1;// A先走dif步for(int i =0;i < diff;++i){ pb = pb->next;}}while(pa !=nullptr&& pb !=nullptr){if(pa == pb){return pa;} pa = pa->next; pb = pb->next;}returnnullptr;}时间复杂度分析：O(m +n),其中 m + n分别是headA和headB的长度。
2.2.3.7 两两交换链表中的节点 24.
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100
解题思路：
1 交换相邻的两个节点；
ListNode*swapPairs(ListNode* head){ ListNode *dummyHead =newListNode(-1); dummyHead->next = head; ListNode *current = dummyHead;// 保证够两个节点while(current->next !=nullptr&& current->next->next !=nullptr){// 记录连续相邻的两个节点 ListNode *temp1 = current->next; ListNode *temp2 = current->next->next->next; current->next = current->next->next;// 步骤1 current->next->next = temp1;// 步骤2 current->next->next->next = temp2;// 步骤3// current 移动两位，准备下一轮交换 current = current->next->next;// 移动两位} std::unique_ptr<ListNode>ptr(dummyHead);return dummyHead->next;}2.2.3.8 链表刷题总结
翻转链表：使用头插入法。如果链表没有头节点，那就new一个头结点，使用一个指针指向头结点，另一个指针指向头的下一个节点；然后头部指针和下一个节点指针断开；当p!=nullptr时，依次采用头插入方式插入。核心插入如下：
p->next = phead->next
phead->next = p;
p = p->next;
删除倒数第N个节点：使用双指针方法，头指针先移动N个节点，然后两个指针一起移动，判断条件时，p->next != nullptr时，直接返回。最后q指向的待删除节点的前一个节点。
链表相交：使用双指针，各自遍历一遍链表，对比两个链表长度，长度长的链表先向前移动diff = len1 – len2个元素，然后一起移动；每次移动都判断是否相等，相等的就是交点。
环形链表：x + y + z + y = 2(x + y),最后得出x = z,也就是快指针到相遇节点与慢指针从头到相遇节点的距离相同。
