难度 | 完成日期 | 耗时 | 提交次数 |
---|---|---|---|
中等 | 2020-1-16 | 1 小时 | 1 |
问题描述
反转从位置 m 到 n 的链表. 请使用一趟扫描完成反转.
说明:
1 ≤ m ≤ n ≤ 链表长度.
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解题思路
普通方法
- ListNode* reverseBetween(ListNode* head, int m, int n) {
- ListNode *_head = head;
- int count = n - m + 1;
- ListNode *former;
- if (m == 1) {
- former = nullptr;
- } else {
- for (int i = 0 ; i <m - 2; i++) {
- head = head->next;
- }
- former = head;
- head = head->next;
- }
- int data[count];
- for (int i = 0; i <count; i++) {
- data[i] = head->val;
- head = head->next;
- }
- ListNode *reverse = new ListNode(0);
- ListNode *reverseH = reverse;
- for (int i = 0; i <count; i++) {
- ListNode *temp = new ListNode(data[count - i - 1]);
- reverse->next = temp;
- reverse = reverse->next;
- }
- reverse->next = head;
- if (m == 1) {
- return reverseH->next;
- } else {
- former->next = reverseH->next;
- return _head;
- }
- }
一次遍历中把位置 m 到 n 中的所有数据保存, 再重新组成链表接在前一个链表结尾, 再将原链表未遍历部分接在新的链表尾部.
来源: http://www.bubuko.com/infodetail-3383947.html