链表练习题主要包括链表逆序，链表判环和链表排序。
/************************************************************************* > File Name: reverse_list.cpp > Author: Yuji CAO > Mail: yujicao@amazon.com > Created Time: 2016年08月12日 星期五 09时19分24秒 ************************************************************************/ #include<iostream> #include<vector> #include<unordered_map> #include<unordered_set> #include<sstream> #include<list> #include<queue> #include<stack> #include<string> #include<utility> #include<algorithm> using namespace std; namespace linear_table { struct Node { int val; Node* next; Node(int val):val(val),next(nullptr){}; }; static Node* mkList(vector<int> data) { Node* head = new Node(data[0]); Node* ans = head; for (int i = 1; i < data.size(); ++i) { head->next = new Node(data[i]); head = head->next; } head->next = nullptr; return ans; } static void visit(Node* list) { while(list != nullptr) { cout<<list->val<<","; list=list->next; } cout<<endl; } class List { public: /* * root. * 3->1->4->6->10->null * 1->null;3;4->6->10->null <1,10> * root.left. * 1->null <1,1> * root.right * 4->6->10->null * 4->null;6;10->null <4,10> * root.right.left * 4->null <4,4> * root.right.right * 10->null <10,10> */ Node* sort(Node* root) { return qSort(root).first; } /* 1. 1->2->3->4 1<->2<-3<-4 2. 2->3->4 2<->3<-4 3. 3->4 3<->4 4. 4 4 set newHead */ Node* reverseList(Node* head) { Node* newHead = nullptr; Node* tail = reverseInner(head, newHead); tail->next = nullptr; return newHead; } /* * 1->2->3->4->5->6 * ^ v * 11 7 * ^ v * 10<-9<-8 */ int crossPos(Node* head) { Node* qPtr = head->next; Node* sPtr = head; while (qPtr != nullptr && sPtr != nullptr) { if (qPtr == sPtr) { Node* iPtr = head; int i = 0; qPtr = qPtr->next; while(iPtr != qPtr) { iPtr = iPtr->next; qPtr = qPtr->next; i++; } return i; } qPtr = qPtr->next; if (qPtr == nullptr) break; qPtr = qPtr->next; sPtr = sPtr->next; } return -1; } bool isCircled(Node* head) { Node* qPtr = head; Node* sPtr = head->next; while (qPtr != nullptr && sPtr != nullptr) { if (qPtr == sPtr) { return true; } qPtr = qPtr->next; if (qPtr == nullptr) return false; qPtr = qPtr->next; sPtr = sPtr->next; } return false; } private: Node* reverseInner(Node* head, Node*& newHead) { if (head->next == nullptr) { newHead = head; return head; } Node* tail = reverseInner(head->next, newHead); tail->next = head; return head; } //1->3->2->5->4 pair<Node*, Node*> split(Node* head) { if (head == nullptr) return pair<Node*, Node*>(head, head); Node* left = nullptr; Node* leftHead = nullptr; Node* right = nullptr; Node* rightHead = nullptr; Node* pivot = head; head = head->next; while(head != nullptr) { if(pivot->val <= head->val) { if (leftHead == nullptr) { leftHead = head; left = head; } else { left->next = head; left = left->next; } } else { if (rightHead == nullptr) { rightHead = head; right = head; } else { right->next = head; right = right->next; } } head = head->next; } if (left) left->next = nullptr; if (right) right->next = nullptr; return pair<Node*, Node*>(leftHead, rightHead); } pair<Node*, Node*> qSort(Node* head) { pair<Node*, Node*> ans = split(head); pair<Node*, Node*> ret; if (ans.first) { pair<Node*, Node* > l = qSort(ans.first); if (ans.second) { pair<Node*, Node*> r = qSort(ans.second); l.second->next = head; head->next = r.first; r.second->next = nullptr; ret.first = l.first; ret.second = r.second; } else { l.second->next = head; head->next = nullptr; ret.first = l.first; ret.second = head; } } else { if (ans.second) { pair<Node*, Node*> r = qSort(ans.second); r.second->next = head; head->next = r.first; r.second->next = nullptr; ret.first = head; ret.second = r.second; } else { head->next = nullptr; ret.first = head; ret.second = head; } } return ret; } }; }; int main() { linear_table::List lt; int N = 0; cin>>N; vector<int> data; for (int i = 0; i < N; ++i) { int a; cin>>a; data.push_back(a); } linear_table::Node* head = linear_table::mkList(data); linear_table::visit(head); linear_table::visit(lt.reverseList(head)); linear_table::Node* head1 = linear_table::mkList(data); linear_table::Node* cur = head1; int c = 0; cin>>c; for (int i = 0; i < c; ++i) { cur = cur->next; } linear_table::Node* cross = cur; while (cur->next != nullptr) { cur = cur->next; } cur->next = cross; cout<<lt.isCircled(head1)<<endl; cout<<lt.isCircled(head)<<endl; cout<<lt.crossPos(head1)<<endl; cout<<lt.crossPos(head)<<endl; linear_table::Node* head2 = linear_table::mkList(data); linear_table::visit(head2); linear_table::Node* ans = lt.sort(head2); while (ans) { cout<<ans->val<<","; ans = ans->next; } cout<<endl; return 0; }