反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL
1 #include "_000库函数.h" 2 3 4 struct ListNode { 5 int val; 6 ListNode *next; 7 ListNode(int x) : val(x), next(NULL) {} 8 }; 9 10 11 //只能扫描一遍12 //将中间要反转的数取出来在放入链表中13 class Solution {14 public:15 ListNode* reverseBetween(ListNode* head, int m, int n) {16 if (!head || m <= 0 || n <= 0 || n <= m)return head;17 //加头18 ListNode*p = new ListNode(-1);19 p->next = head;20 head = p;21 22 stack s;23 ListNode*pre = new ListNode(0);24 while (p && n >0) {25 --m;26 if (m == 0)pre = p; 27 p = p->next;28 if (p && m <= 0)29 s.push(p->val);30 --n;31 }32 if (p == NULL)return head->next;//m,n超过了链表长度33 pre->next = p->next;34 while (!s.empty()) {35 ListNode*q = new ListNode(0);36 q->val = s.top();37 q->next = pre->next; 38 pre->next = q;39 pre = q;40 s.pop();41 }42 return head->next;43 }44 };45 46 //走一步反转一个数据47 //不用对m,n的大小进行判断48 class Solution {49 public:50 ListNode *reverseBetween(ListNode *head, int m, int n) {51 ListNode *dummy = new ListNode(-1), *pre = dummy;52 dummy->next = head;53 for (int i = 0; i < m - 1; ++i) pre = pre->next;54 ListNode *cur = pre->next;55 for (int i = m; i < n; ++i) { //用交换法56 ListNode *t = cur->next;57 cur->next = t->next;58 t->next = pre->next;59 pre->next = t;60 }61 return dummy->next;62 }63 };64 65 66 void T092() {67 Solution s;68 vector v;69 ListNode *head = new ListNode(0);70 ListNode *p = head;71 v = { 1,2,3,4,5 };72 for (auto a : v) {73 ListNode *q = new ListNode(0);74 q->val = a;75 p->next = q;76 p = q;77 }78 p = head->next;79 while (p) {80 cout << p->val << "->";81 p = p->next;82 }83 cout << endl;84 85 86 p = s.reverseBetween(head->next, 2, 6);87 while (p) {88 cout << p->val << "->";89 p = p->next;90 }91 cout << endl;92 }