2 链表
链表
1 链表基础理论
什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
- 单链表
- 双链表
- 循环链表
链表在内存中不是连续分布的，是通过指针串联在一起的
链表的定义
struct ListNode{
int val;
ListNode *next = nullptr;
ListNode(int x) : val(x), next(nullptr);
}；
性能分析
| 插入/删除(时间复杂度) | 查询(时间复杂度) | 适用场景 | |
|---|---|---|---|
| 数组 | O(n) | O(1) | 数据量固定，频繁查询，较少增删 |
| 链表 | O(1) | O(n) | 数据量不固定，频繁增删，较少查询 |
2一处链表元素
力扣题目链接
题目：
题意：删除链表中等于给定值 val 的所有节点。
示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]
思路：
使用虚拟头节点dummy node
代码：
class Solution {
public:
struct ListNode{
int val;
ListNode* next =nullptr;
ListNode(x): val(x),next(nullptr);
};
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyNode = new ListNode(0);
dummyNode->next = head;
ListNode* cur = dummyNode;
while (cur->next != NULL){
if(cur->next->val == val){
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
}else{
cur = cur->next;
}
}
return dummyNode->next;
}
};
3 设计链表
力扣题目链接
题目：
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
思路：
这道题目设计链表的五个接口：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
同样使用虚拟头节点dummyHead
代码：
class MyLinkedList {
public:
struct LinkedNode{
int val;
LinkedNode* next;
LinkedNode(int x): val(x), next(nullptr){}
};
MyLinkedList() {
_dummyhead = new LinkedNode(0);
_size = 0;
}
int get(int index) {
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur=_dummyhead->next;
while(index--){
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode* cur = new LinkedNode(val);
cur->next = _dummyhead->next;
_dummyhead->next = cur;
_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyhead;
while(cur->next!=nullptr){
cur = cur->next;
}
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
LinkedNode* cur = _dummyhead;
//if(index<0) index =0;
if(_size < index) return;
while(index--){
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = new LinkedNode(val);
cur->next->next = tmp;
_size++;
}
void deleteAtIndex(int index) {
LinkedNode* cur = _dummyhead;
if(_size <= index || index < 0) return;
while(index--){
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
tmp=nullptr;
_size--;
}
private:
int _size;
LinkedNode* _dummyhead;
};
4 翻转链表
力扣题目链接
题目：
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路：
双指针法，一个slow保存当前指针，一个fast保存下一个指针，再定义一个临时指针tmp保存fast指针的下一个节点，挨个反转即可(fast->next=slow)
代码：
ListNode* reverseList(ListNode* head) {
ListNode *slow = nullptr;
ListNode *fast = head;
ListNode *tmp;
if(head == nullptr) return nullptr;
while(fast != nullptr){
tmp = fast->next;
fast->next=slow;
slow = fast;
fast = tmp;
}
return slow;
}
5 两两交换链表中的节点
力扣题目链接
题目：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路：
模拟过程，以三步一个循环，主要注意边界条件，
代码：
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while(cur->next!=nullptr&&cur->next->next!=nullptr){
ListNode*tmp1 = cur->next;
ListNode*tmp2 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = tmp1;
cur->next->next->next = tmp2;
cur = cur->next->next;
}
return dummyHead->next;
}
6 删除链表的倒数第N个节点
力扣题目链接
题目：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路：
虚拟头节点+双指针，计数fast指针计数n后slow指针再动，终止条件fast为空。
代码：
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummyhead = new ListNode(0);
dummyhead -> next = head;
ListNode*fast=dummyhead;
ListNode*slow=dummyhead;
while(n--){
fast = fast->next;
}
while(fast->next!=nullptr){
fast=fast->next;
slow=slow->next;
}
slow->next=slow->next->next;
return dummyhead->next;
}
7 链表相交
力扣题目链接
题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路：
相交节点，注意是指针相同，注意相交一定在某一个交点后完全相同，先求得两个链表的长度，假设长度n1>=n2，然后将较长的链表移动n1-n2步，判断与较短链表头节点是否相等
代码：
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *curA = headA;
ListNode *curB = headB;
int lengthA = 0;
int lengthB = 0;
while(curA != NULL){
lengthA++;
curA = curA->next;
}
while(curB != NULL){
lengthB++;
curB = curB->next;
}
int lengthNum;
if(lengthA < lengthB){
swap(lengthA,lengthB);
curA = headB;
curB = headA;
}
else{
curA = headA;
curB = headB;
}
lengthNum = lengthA - lengthB;
while(lengthNum--){
curA = curA->next;
}
while(curA!= NULL){
if(curA== curB) return curA;
curB = curB->next;
curA = curA->next;
}
return NULL;
}
8 环形链表Ⅱ
力扣题目链接
题目：
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
思路：
可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。且通过公式计算可以得到fast与head同时后移到相遇的位置就是环的入口。
代码：
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow =slow->next;
if(fast == slow){
ListNode *node1 = head;
ListNode *node2 = fast;
while(node1!=node2){
node1=node1->next;
node2=node2->next;
}
return node2;
}
}
return NULL;
}