链表

反转链表 原题链接：https://leetcode.cn/problems/reverse-linked-list/ 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 1.利用外部空间主要思路：利用外部空间+STL算法 先申请一个动态扩容的数组或者容器，然后不断遍历链表，将链表中的元素添加到这个容器中。 再利用容器自身的 API，反转整个容器，这样就达到反转的效果了。 最后同时遍历容器和链表，将链表中的值改为容器中的值。 12345678910111213141516class Solution {public: int divide(int dividend, int divisor) { int flag = 0; int count = 0; if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1; dividend = abs(dividend); divisor = abs(divisor); while (dividend - divisor >= 0) { dividend -= divisor; count++; } if (flag) count = -count; return count; }}; 2.双指针迭代3.优化的双指针4.递归

删除链表中所有值为x的元素 1.不带头结点（1）不带头结点递归删除 递归算法 删除不带头结点的单链表 L 中所有值为 x 的结点 12345678910111213141516171819202122232425262728#include "presetNoHead.h"//利用递归 删除指定元素void recursiveDelete(Node *&L, int x) { Node *p = L; if (L == NULL) return;//递归出口 if (L->data == x) { L = L->next;//L->next = L->next->next; free(p); recursiveDelete(L, x); } else { recursiveDelete(L->next, x);//L = L->next; }}int main() { int n; Node list; Node *L = &list; cout << "enter the length of this linklist : "; cin >> n; createLinkList(L, n); cout << "current linklist: " << endl; print(L); int x; cout << "enter the target : "; cin >> x; recursiveDelete(L, x); cout << "after the deletion : "; print(L); return 0;} （2）不带头结点非递归删除1234567891011121314151617181920212223242526272829303132333435363738394 ...

反向输出每个结点的值 L为不带头结点的单链表， 编写算法实现从尾到头 反向输出每个结点的值， 123456789101112131415161718192021#include "presetNoHead.h"void rPrint(Node *L) { if (L != NULL) { rPrint(L->next); cout << L->data << " "; } else { return; }}int main() { Node list; Node *L = &list; int n; cout << "enter the length of this linklist : "; cin >> n; createLinkList(L, n); cout << "current linklist: " << endl; print(L); cout << "Reverse order : "; rPrint(L); return 0;}

删除链表中的最小元素 L为带头结点的单链表 编写算法实现 删除一个最小值结点的高效算法 12345678910111213141516171819202122232425#include "presetHead.h"void minDelete(LinkList &L) { Node *p = L; Node *preMin = L;//指向最小值所存储的结点 的前一个结点 while (p->next != NULL) { if (p->next->data < preMin->next->data) { preMin = p; } p = p->next; } Node *q = preMin->next; preMin->next = q->next; free(q);}int main() { int n; cout << "enter the length of this linklist : "; cin >> n; LinkList L; createLinkList(L, n); cout << "current linklist: "; print(L); minDelete(L); cout << "after the deletion : "; print(L); return 0;}

链表原地翻转 带有头结点的单链表L 单链表就地逆置，要求辅助空间复杂度为O(1) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>using namespace std;typedef struct Node { int data; struct Node *next;} Node, *LinkList;//头插法建立链表（有头结点）void createLinkList(LinkList &L, int n) { L = new Node; L->next = NULL; for (int i = 0; i < n; ++i) { Node *p = (Node *)malloc(sizeof(Node)); cin >> p->data; p->next = NULL; p->next = L->next; L->next = p; }}//链表数据打印void print(LinkList L) { Node *p = L->next; while (p != NULL) { //cout << p->data << ":" << p->next << " "; cout << p->data << " "; p = p->next; } cout << endl;}//利用头插法实现链表逆置void reverse(LinkList &L) { if (L == NULL) return; Node *p ...

链表插入排序

回文链表 原题链接：https://leetcode.cn/problems/aMhZSa/ 给定一个链表的 头节点 head ，请判断其是否为回文链表。 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 1.试解栈123456789101112131415161718192021class Solution {public: bool isPalindrome(ListNode* head) { if (head->next == nullptr) return true; //1.stk push stack<ListNode*> stk; ListNode* p = head; while (p) { stk.push(p); p = p->next; } //2.traverse linklist p = head; while (p) { if (stk.top()->val != p->val) return false; stk.pop(); p = p->next; } return true; }}; 2.数组+双指针1 3.递归1 4.快慢指针1

两个链表的第一个重合节点 原题链接：https://leetcode.cn/problems/3u1WK4/ 给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 函数返回结果后，链表必须 保持其原始结构 。 1.哈希表主要思路： 遍历listA将其中的结点全部标记存入unset中（哈希表） 遍历listB直到其中出现相同的next域的值 直接返回其值即为结果 若遍历listB都完都没有出现符合要求的结果则返回nullptr 1234567891011121314151617181920//注：将unordered_set放到成员方法内部可以提高时间效率class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> unset; //1.initialize unset ListNode* tmp = headA; while (tmp) { unset.insert(tmp); tmp = tmp->next; } //2.find the first node tmp = headB; while (tmp) { if (unset.count(tmp)) return tmp; tmp = tmp->next; } return nullptr; }}; 时间：48ms 内存：16.24mb 时间复杂度：$O(N)$ 空间复杂度：$O(N)$ 2.双指针主要思路： 首先判断链表是否为空，如果其中有一个链表为空则两个链表一定不相交返回nullptr 当链表都不为空时 创建两个指 ...

链表中环的入口节点 原题链接：https://leetcode.cn/problems/c32eOV/ 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 注意 pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 1.哈希表思路： 利用哈希表建立一个标记数组 用于标记已经出现的next指针域 while循环遍历链表 直到出现重复的next指针域 表示链表环开始出现 返回此时的链表结点指针 即为环入口结点 unordered_map1234567891011121314class Solution {public: unordered_map<ListNode*, int> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark[p]) return p; mark[p] = 1; p = p->next; } return nullptr; }}; 时间：12ms 内存：9.8mb unordered_set12345678910111213public: unordered_set<ListNode*> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark. ...

删除链表的倒数第 n 个结点 原题链接：https://leetcode.cn/problems/SLwz0R/ 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 1.计算链表长度一种最容易想到的方法：（无虚拟头结点） 首先从头节点开始对链表进行一次遍历，得到链表的长度length 然后从头节点开始对链表进行一次遍历，当遍历到第L−n+1个节点时，其下一个就是需要删除的节点 1234567891011121314151617181920212223242526272829303132333435363738class Solution {public: int getLength(ListNode *head) { int length = 0; while (head) { head = head->next; length++; } return length; } ListNode* removeNthFromEnd(ListNode *head, int n) { if (head == nullptr) return nullptr; int listSize = getLength(head); if (n < 1 || n > listSize) return nullptr;// 1 <= n <= len ListNode* deleteNode; if (n == listSize) { //delete the firstNode deleteNode = head; head = head->next; } else { ListNode* p = head; int ind = listSize - n - 1; while (ind--) p = p->n ...