CCF-CSP备战NO.5链表

1.单向链表的构造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) {} };方式一 适合少量节点ListNode* head new ListNode(1); head-next new ListNode(2); head-next-next new ListNode(3);方式二 用数组批量构造最常用面试题标准写法ListNode* createList(const vectorint arr) { if (arr.empty()) return nullptr; ListNode* head new ListNode(arr[0]); ListNode* cur head; for (int i 1; i arr.size(); i) { cur-next new ListNode(arr[i]); cur cur-next; } return head; }调用vectorint nums {1, 2, 3, 4, 5}; ListNode* list createList(nums);方式3带头节点的哑结点dummy nodeListNode* dummy new ListNode(-1); // 值随便填 ListNode* cur dummy; for (int val : arr) { cur-next new ListNode(val); cur cur-next; } ListNode* realHead dummy-next; // 这才是真正的头 // 用完记得 delete dummy2.链表基础一、创建与销毁1. 创建节点ListNode* createNode(int val) { return new ListNode(val); }2. 根据数组创建链表ListNode* createList(const vectorint arr) { if (arr.empty()) return nullptr; ListNode* head new ListNode(arr[0]); ListNode* cur head; for (int i 1; i arr.size(); i) { cur-next new ListNode(arr[i]); cur cur-next; } return head; }3. 销毁链表防止内存泄漏void deleteList(ListNode* head) { while (head ! nullptr) { ListNode* temp head; head head-next; delete temp; } }二、遍历与查找4. 遍历链表void traverse(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { cout cur-val ; cur cur-next; } cout endl; }5. 递归遍历反向打印void printReverse(ListNode* head) { if (head nullptr) return; printReverse(head-next); cout head-val ; }6. 查找某个值是否存在bool findValue(ListNode* head, int target) { ListNode* cur head; while (cur ! nullptr) { if (cur-val target) return true; cur cur-next; } return false; }7. 获取链表长度int getLength(ListNode* head) { int len 0; while (head ! nullptr) { len; head head-next; } return len; }8. 获取第k个节点k从1开始ListNode* getKthNode(ListNode* head, int k) { int count 1; while (head ! nullptr count k) { head head-next; count; } return head; // 如果k超出范围返回nullptr }三、插入操作9. 头插法ListNode* insertAtHead(ListNode* head, int val) { ListNode* newNode new ListNode(val); newNode-next head; return newNode; // 返回新的头节点 }10. 尾插法ListNode* insertAtTail(ListNode* head, int val) { ListNode* newNode new ListNode(val); if (head nullptr) return newNode; ListNode* cur head; while (cur-next ! nullptr) { cur cur-next; } cur-next newNode; return head; }11. 在指定位置插入位置从1开始ListNode* insertAtPosition(ListNode* head, int val, int pos) { if (pos 1) return insertAtHead(head, val); ListNode* newNode new ListNode(val); ListNode* cur head; // 找到第pos-1个节点 for (int i 1; i pos - 1 cur ! nullptr; i) { cur cur-next; } if (cur nullptr) { // 位置超出范围插入到尾部 return insertAtTail(head, val); } newNode-next cur-next; cur-next newNode; return head; }12. 在某个节点后面插入已知该节点void insertAfterNode(ListNode* node, int val) { if (node nullptr) return; ListNode* newNode new ListNode(val); newNode-next node-next; node-next newNode; }四、删除操作13. 删除头节点ListNode* deleteHead(ListNode* head) { if (head nullptr) return nullptr; ListNode* newHead head-next; delete head; return newHead; }14. 删除尾节点ListNode* deleteTail(ListNode* head) { if (head nullptr) return nullptr; if (head-next nullptr) { delete head; return nullptr; } ListNode* cur head; while (cur-next-next ! nullptr) { cur cur-next; } delete cur-next; cur-next nullptr; return head; }15. 删除指定值的节点只删第一个ListNode* deleteByValue(ListNode* head, int val) { if (head nullptr) return nullptr; // 如果要删除的是头节点 if (head-val val) { ListNode* newHead head-next; delete head; return newHead; } ListNode* cur head; while (cur-next ! nullptr cur-next-val ! val) { cur cur-next; } if (cur-next ! nullptr) { ListNode* toDelete cur-next; cur-next cur-next-next; delete toDelete; } return head; }16. 删除指定位置的节点位置从1开始ListNode* deleteAtPosition(ListNode* head, int pos) { if (head nullptr) return nullptr; if (pos 1) return deleteHead(head); ListNode* cur head; for (int i 1; i pos - 1 cur ! nullptr; i) { cur cur-next; } if (cur nullptr || cur-next nullptr) { return head; // 位置超出范围 } ListNode* toDelete cur-next; cur-next cur-next-next; delete toDelete; return head; }17. 删除所有值为val的节点ListNode* deleteAllByValue(ListNode* head, int val) { // 先处理头节点连续等于val的情况 while (head ! nullptr head-val val) { ListNode* temp head; head head-next; delete temp; } if (head nullptr) return nullptr; ListNode* cur head; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* temp cur-next; cur-next cur-next-next; delete temp; } else { cur cur-next; } } return head; }五、修改操作18. 修改第k个节点的值void updateValue(ListNode* head, int k, int newVal) { ListNode* node getKthNode(head, k); if (node ! nullptr) { node-val newVal; } }六、进阶操作19. 合并两个有序链表ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); // 哑节点 ListNode* cur dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next (l1 ! nullptr) ? l1 : l2; return dummy.next; }20. 判断链表是否有环快慢指针bool hasCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }21. 找到环的入口节点ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; // 第一次相遇 while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) break; } if (fast nullptr || fast-next nullptr) return nullptr; // 从头开始同步移动直到相遇 slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }22. 找到两个链表的交点ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { if (headA nullptr || headB nullptr) return nullptr; ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; }23. 两两交换相邻节点ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (prev-next ! nullptr prev-next-next ! nullptr) { ListNode* first prev-next; ListNode* second prev-next-next; // 交换 first-next second-next; second-next first; prev-next second; prev first; } return dummy.next; }七、排序相关24. 链表归并排序ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) return head; // 找中点 ListNode* slow head; ListNode* fast head; ListNode* prev nullptr; while (fast ! nullptr fast-next ! nullptr) { prev slow; slow slow-next; fast fast-next-next; } prev-next nullptr; // 断开链表 // 递归排序 ListNode* left sortList(head); ListNode* right sortList(slow); return mergeTwoLists(left, right); }3.经典例题1反转链表#include bits/stdc.h using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* nextTemp curr-next; curr-next prev; prev curr; curr nextTemp; } return prev; } void printList(ListNode* head) { while (head ! nullptr) { cout head-val ; head head-next; } cout endl; } int main() { // 从输入构造数组 vectorint arr; int num; while (cin num) { arr.push_back(num); } // 判断数组是否为空 if (arr.empty()) return 0; // 构造链表 ListNode* head new ListNode(arr[0]); ListNode* cur head; for (int i 1; i arr.size(); i) { cur-next new ListNode(arr[i]); cur cur-next; } ListNode* reversed reverseList(head); printList(reversed); return 0; }