企业官网建设流程全解析

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 vector<int>& 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; }

调用

vector<int> nums = {1, 2, 3, 4, 5}; ListNode* list = createList(nums);

方式3：带头节点的哑结点（dummy node）

ListNode* dummy = new ListNode(-1); // 值随便填 ListNode* cur = dummy; for (int val : arr) { cur->next = new ListNode(val); cur = cur->next; } ListNode* realHead = dummy->next; // 这才是真正的头 // 用完记得 delete dummy

2.链表基础

一、创建与销毁

1. 创建节点

ListNode* createNode(int val) { return new ListNode(val); }

2. 根据数组创建链表

ListNode* createList(const vector<int>& 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() { // 从输入构造数组 vector<int> 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; }