Problem:
反转单向和双向链表 【题目】 分别实现反转单向链表和反转双向链表的函数。 【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间 复杂度要求为O(1)Solution:
学会使用指针Code:
1 #pragma once 2 3 #include4 5 using namespace std; 6 7 struct Node 8 { 9 int val; 10 Node* next; 11 Node(int a = 0) :val(a), next(NULL) {} 12 }; 13 14 void ReverSingleList(Node*& head)//反转单向链表 15 { 16 if (head->next == NULL || head->next->next == NULL) 17 return; 18 Node *p1, *p2, *p3; 19 p1 = head->next; 20 p2 = p1->next; 21 p3 = p2->next; 22 p1->next = NULL; 23 while (p3) 24 { 25 p2->next = p1; 26 p1 = p2; 27 p2 = p3; 28 p3 = p3->next; 29 } 30 p2->next = p1; 31 head->next = p2; 32 } 33 34 35 struct DNode 36 { 37 int val; 38 DNode* next; 39 DNode* pre; 40 DNode(int a = 0) :val(a), next(NULL),pre(NULL) {} 41 }; 42 43 void ReverDoubleList(DNode*& head)//反转双向链表，方法与单向链表一样 44 { 45 if (head->next == NULL || head->next->next == NULL) 46 return; 47 DNode *p1, *p2, *p3; 48 p1 = head->next; 49 p2 = p1->next; 50 p3 = p2->next; 51 p1->next = NULL; 52 p1->pre = p2; 53 while (p3) 54 { 55 p2->next = p1; 56 p1->pre = p2; 57 p2->pre = p3; 58 p1 = p2; 59 p2 = p3; 60 p3 = p3->next; 61 } 62 p2->next = p1; 63 p2->pre = head; 64 head->next = p2; 65 } 66 67 void Test() 68 { 69 int a[6] = { 1,2,3,4,5,6 }; 70 Node* head = new Node(-1); 71 Node* p = head; 72 for (auto n : a) 73 { 74 Node* q = new Node(n); 75 p->next = q; 76 p = q; 77 } 78 p->next = NULL; 79 80 p = head->next; 81 cout << "原链表为： "; 82 while (p) 83 { 84 cout << p->val << "->"; 85 p = p->next; 86 } 87 88 ReverSingleList(head); 89 p = head->next; 90 cout << endl << "*******************" << endl << "反转后的链表为： "; 91 while (p) 92 { 93 cout << p->val << "->"; 94 p = p->next; 95 } 96 cout << endl << "=============================" << endl; 97 cout << "=============================" << endl; 98 cout << "=============================" << endl; 99 100 101 int b[6] = { 1,2,3,4,5,6 };102 DNode* head2 = new DNode(-1);103 DNode* p2 = head2;104 for (auto n : b)105 {106 DNode* q2 = new DNode(n);107 p2->next = q2;108 q2->pre = p2;109 p2 = q2;110 }111 p2->next = NULL;112 113 p2 = head2->next;114 cout << "原链表为的顺为： ";115 while (p2->next)116 {117 cout << p2->val << "->";118 p2 = p2->next;119 }120 cout << p2->val << "->";121 cout << endl << "*******************" << endl << "原链表为的逆为： ";122 while (p2->pre)123 {124 cout << p2->val << "->";125 p2 = p2->pre;126 }127 128 ReverDoubleList(head2);129 p2 = head2->next;130 cout << endl << "*******************" << endl << "反转后的双向链表的顺为： ";131 while (p2->next)132 {133 cout << p2->val << "->";134 p2 = p2->next;135 }136 cout << p2->val << "->";137 cout << endl << "*******************" << endl << "反转后的双向链表的逆为： ";138 while (p2->pre)139 {140 cout << p2->val << "->";141 p2 = p2->pre;142 }143 cout << endl << "=============================" << endl;144 }