链表是一种常见的线性数据结构，由一系列的节点组成，每个节点由两部分组成：数据域和指针域。数据域用于存储节点的数据，而指针域用于指向下一个节点，从而形成一系列的连接。
基本概念：
节点：链表中的基本单元，包含数据和指向下一个节点的指针。
头节点：链表的第一个节点，通常用来标识链表的起始位置。
尾节点：链表的最后一个节点，其指针通常指向空值（null），表示链表的结束。
单向链表：每个节点只包含一个指向下一个节点的指针。
双向链表：每个节点包含两个指针，分别指向前一个节点和后一个节点，使得可以双向遍历链表。
数组和链表的对比
访问速度：数组>链表，数组可以随机访问元素O(1)，而链表只能挨个访问O(n)
插入删除：链表>数组，数组需要把插入位置前面的元素以前或者把删除位置后面的元素移前O(n），链表是O(1),如果插入的位置是中间，需要遍历到当前位置O(n）。
题目：
160. 相交链表 - 力扣（LeetCode）
206. 反转链表 - 力扣（LeetCode）
234. 回文链表 - 力扣（LeetCode）
141. 环形链表 - 力扣（LeetCode）
142. 环形链表 II - 力扣（LeetCode）
21. 合并两个有序链表 - 力扣（LeetCode）
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
92. 反转链表 II - 力扣（LeetCode）
148. 排序链表 - 力扣（LeetCode）
23. 合并 K 个升序链表 - 力扣（LeetCode）
相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
思路：定义两个指针p1和p2分别指向headA和headB，每次走一步，为NULL时指向对方头节点，直到相遇。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1,*p2;p1 = headA,p2 = headB;while(p1 != p2){p1 = p1 == NULL ? headB : p1->next;p2 = p2 == NULL ? headA : p2->next;}return p1;}
};反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *pre,*cur,*next;pre = nullptr,cur = head;while(cur) {next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}
};回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {/1.栈// stack<int> st;// ListNode* p1 = head;// while(p1){// st.push(p1->val);// p1 = p1->next;// }// p1 = head;// while(p1){// if(p1->val != st.top()){// return false;// }// st.pop();// p1 = p1->next;// }// return true;//2.找中间节点+翻转链表+扫描//找midListNode *mid = FindMid(head);ListNode * p1 = head,*p2 = mid->next;//翻转ListNode *pre = nullptr,*next;while(p2){next = p2->next;p2->next = pre;pre = p2;p2 = next;}p2 = pre;while(p2){cout<<p1->val<<" "<<p2->val<<endl;if(p1->val != p2->val) return false;p1 = p1->next;p2 = p2->next;}return true;}ListNode* FindMid(ListNode* head){ListNode *slow,*fast;slow = fast = head;while(fast->next && fast->next->next){slow = slow->next;fast = fast->next->next;}return slow;}
};环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路：定义两个指针slow，fast，slow每次走一步，fast每次走两步，如果fast可以走到头说明不成环，如果两者相遇，这说明是一个环形链表，接着让fast或者slow重新指向头结点head，然后每次走一步，两者相遇时即为入口节点。
问题1：为什么两者可以完美相遇，而不是错开？
因为当slow进入环入口时，fast已经在环中了，假设两者相距x步，由于每次循环fast都比slow多走一步，那么每一次它们的距离就会-1，经过x步，两者距离为0，一定相遇。
问题2：为什么重新回到head再相遇的相遇点就是环入口？
证明如下：
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* ans,*p1,*p2,*p3;ans = new ListNode(-1);p1 = list1,p2 = list2,p3 = ans;while(p1 && p2){if(p1->val < p2->val){p3->next = p1;p1 = p1->next;}else{p3->next = p2;p2 = p2->next;}p3 = p3->next;}while(p1){p3->next = p1;p1 = p1->next;p3 = p3->next;}while(p2){p3->next = p2;p2 = p2->next;p3 = p3->next;}return ans->next;}
};删除链表倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {//1.获取倒数第n-1个节点// ListNode* phead = new ListNode(-1);// phead->next = head;// ListNode* fast,*slow;// fast = slow = phead;// while(n--){// fast = fast->next;// }// while(fast->next){// slow = slow->next;// fast = fast->next;// }// //此时slow是倒数第n-1个节点// slow->next = slow->next->next;// return phead->next;//2.stack栈ListNode* cur = head;stack<ListNode*> st;while(cur){st.push(cur);cur = cur->next;}while(n--){st.pop();}if(st.empty()) return head->next;cur = st.top();cur->next = cur->next->next;return head;}
};反转链表II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
穿针引线步骤：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode*phead=new ListNode(-1);phead ->next = head;ListNode* cur,*next,*pre;pre = phead;for(int i = 0;i < left - 1;i++){pre = pre->next;}cur = pre->next;for(int i = 0;i < right - left;i++){next = cur -> next;cur -> next = next ->next;next -> next = pre->next;pre -> next = next;}return phead->next;}
};排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
基本思路：归并思想
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if(!head || !head->next) return head;// 1.获取中间节点mid---快慢指针ListNode* slow = head;ListNode* fast = head->next;while(fast && fast->next){slow =slow->next;fast = fast->next->next;}ListNode* p1 = head;ListNode* p2 = slow->next;slow->next = nullptr;return Merge(sortList(p1),sortList(p2));}ListNode* Merge(ListNode* p1,ListNode*p2){ListNode* dummy = new ListNode(-1);ListNode* cur = dummy;while(p1 && p2){cout<<cur->val<<endl;if(p1->val < p2->val){cur->next = p1;p1 = p1->next;}else{cur->next = p2;p2 = p2->next;}cur = cur->next;}while(p1){cur->next = p1;p1 = p1->next;cur = cur->next;}while(p2){cur->next = p2;p2 = p2->next;cur = cur->next;}return dummy->next;}
};合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {int l = 0,r = lists.size()-1;return db(lists,l,r);}ListNode* db(vector<ListNode*>&lists,int l,int r){if(l > r){return NULL;}else if(l == r) return lists[l];int mid = (l + r)/2;return Merge(db(lists,l,mid),db(lists,mid+1,r));}ListNode* Merge(ListNode* l1,ListNode* l2){ListNode* p1 = l1,*p2 = l2,*pre = new ListNode(-1);ListNode* p3 = pre;while(p1 && p2){if(p1->val < p2->val){p3->next = p1;p1 = p1->next;}else{p3->next = p2;p2 = p2->next;}p3 = p3->next;}while(p1){p3->next = p1;p1 = p1->next;p3 = p3->next;}while(p2){p3->next = p2;p2 = p2->next;p3 = p3->next;}return pre->next;}
};
