记录下有关链表的一些基本操作，包括创建链表，打印链表，链表长度，找到指定节点，插入节点，删除节点，反转链表，找到中间节点和链表排序。
#include<iostream> #include<vector> using namespace std; struct Node { int val; Node* next; Node(int num):val(num),next(nullptr){} }; Node* CreatList() { Node* head = new Node(0); Node* ptr = head; cout << "Please input a number(q to quit): "; int temp; while (cin >> temp) { Node* newNode = new Node(temp); newNode->next = ptr->next; ptr->next = newNode; ptr = newNode; cout << "Please input a number(q to quit): "; } return head->next; } void ShowList(Node* head) { while (head) { cout << head->val << " "; head = head->next; } cout << endl; } int ListLength(Node* head) { int count = 0; while (head) { count++; head = head->next; } return count; } int FindNode(Node* head, int num) { int count = 0; while (head) { if (head->val == num) return count; count++; head = head->next; } return -1; } Node* InsertList(Node* head, int num, int pos) { Node* newNode = new Node(0), *ptr; newNode->next = head; ptr = newNode; Node* addNode = new Node(num); int count = 0; while (ptr&&count<pos) { count++; ptr = ptr->next; } //需要delete掉newNode addNode->next = ptr->next; ptr->next = addNode; return newNode->next; } Node* DeletNode(Node* head, int pos) { if (pos == 0) return head->next; int count = 1; Node* ptr = head; while (ptr&&count < pos) { count++; ptr = ptr->next; } ptr->next = ptr->next->next; //delete ptr->next; return head; } Node* ReverseList(Node* head) { if (head == nullptr||head->next==nullptr) return head; Node* ptr = ReverseList(head->next); head->next->next = head; head->next = nullptr; return ptr; } int FindMidNode(Node* head) { if (head == nullptr) return -1; Node* newHead = new Node(0); newHead->next = head; Node* left = newHead, *right = newHead; while (right != nullptr&&right->next != nullptr) { left = left->next; right = right->next->next; } return left->val; } Node* SortList(Node* head) { if (head==nullptr||head->next==nullptr) return head; Node* ptr = head; vector<Node*> data; while (ptr) { data.push_back(ptr); ptr = ptr->next; } for (int i = 1; i < data.size(); i++) { Node* temp = data[i]; int j; for (j = i - 1; j >= 0&&data[j]->val > temp->val; j--) data[j + 1] = data[j]; data[j + 1] = temp; } data[0]->next = nullptr; ptr = data[0]; for (int i = 1; i < data.size(); i++) { data[i]->next = ptr->next; ptr->next = data[i]; ptr = data[i]; } return data[0]; } int main() { Node* head = CreatList(); cout << "#1 Creat new List: \n"; ShowList(head); cout << "#2 List length: \n"; cout << ListLength(head) << endl; cout << "#3 Find list node index(val = 2): \n"; cout << FindNode(head, 2) << endl; cout << "#4 Insert a node(999, 0): \n"; head = InsertList(head, 999, 0); ShowList(head); cout << "#5 Delet a node(0): \n"; head = DeletNode(head, 0); ShowList(head); cout << "#6 Reverse a list: \n"; head = ReverseList(head); ShowList(head); cout << "#7 Find list middle value: \n"; cout << FindMidNode(head) << endl; cout << "#8 Sort list: \n"; ShowList(head); head = SortList(head); ShowList(head); return 0; }