链表翻转和排序

链表的翻转链表的部分翻转链表排序

---

链表的翻转

链表的节点由数据域与指针域构成，针对链表的翻转采用三个指针p,q,r，p指向头结点，q指向p的下一个节点，r指向q的下一个节点，p,q,r三个指针遍历整个链表，将q = p->next 写成q->next = p ，因此就将p指向q的指针反转成q指向p。代码如下：

#include <iostream> #include<algorithm> #include<math.h> using namespace std; class Node { public: int data; Node*next; }; class linkList { public: linkList() { head = new Node; head->data = 0; head->next = NULL; } ~linkList() { Node*ptemp, *pdel; ptemp = head; while (ptemp != NULL) { pdel = ptemp; ptemp = ptemp->next; delete pdel; pdel = NULL; } } //创建链表 Node*createList() { int n, value; cout << "请输入您需要创建的链表节点数="; cin >> n; Node*ptemp, *pnew; ptemp = head; for (int i = 0; i < n; i++) { pnew = new Node; pnew->next = NULL; cout << "请输入第" << i + 1 << "个节点的数值="; cin >> pnew->data; ptemp->next = pnew; ptemp = pnew; } return head; } //显示链表 void showList(Node*head) { Node*ptemp = head->next; while (ptemp != NULL) { cout << ptemp->data << " "; ptemp = ptemp->next; } cout << endl; } //获取链表长度 int getLength(Node*head) { Node*ptemp; ptemp = head->next; int count = 0; while (ptemp != NULL) { count++; ptemp = ptemp->next; } return count; } //链表翻转 Node*reverseList(Node*head) { Node*p, *q, *r; p = head; q = head->next; head->next = NULL; r = NULL; while (q != NULL) { r = q->next; q->next = p; p = q; q = r; } head = p; return head; } //显示翻转链表 void showList1(Node*head,int count) { Node*ptemp; ptemp = head; while (count-- > 0) { cout << ptemp->data<<" "; ptemp = ptemp->next; } cout << endl; } private: Node*head; }; int main() { linkList li; Node*head,*head1; head = li.createList(); cout << "链表："; li.showList(head); int count = li.getLength(head); head1 = li.reverseList(head); cout << "翻转后的链表："; li.showList1(head1, count); return 0; }

代码运行结果：

---

链表的部分翻转

对于链表在第m与第个n节点之间翻转，这里采用了只对链表数据域进行操作，将数据域存入到数组中，然后对数组操作。代码如下：

//翻转m与n之间的链表 Node*preverseList(Node*head,int count) { int m, n; Node * ptemp = head; if (head == NULL)return NULL; int arr[10000]; for (int i = 0; i < count; i++) { ptemp = ptemp->next; arr[i] = ptemp->data; } cout << "请输入m与n的值："; cin >> m >> n; while (m <= n) { swap(arr[m-1], arr[n-1]); m++; n--; } ptemp = head; for (int i = 0; i < count; i++) { ptemp = ptemp->next; ptemp->data = arr[i]; } return head; }

代码运行结果：

---

链表排序

链表排序只对数据域进行操作，数据域数据放入数组中即对数组进行排序。代码如下：

//链表排序 Node* sortList(Node* head,int count) { Node * ptemp = head; if (head==NULL)return NULL; int arr[10000]; for (int i = 0; i < count; i++) { ptemp = ptemp->next; arr[i] = ptemp->data; } sort(arr, arr + count); ptemp = head; for (int i = 0; i < count; i++) { ptemp = ptemp->next; ptemp->data = arr[i]; } return head; }

代码运行结果：