题目:
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回反转后的链表。
输入描述:
链表节点数。e.g: 5
依次是链表各节点。e.g:
1
2
3
4
5
left 开始反转位置。e.g: 2
right 结束反转位置。e.g: 3
输出描述:
反转后的链表
样例输入:
5
1
2
3
4
5
2
3
样例输出:
1 3 2 4 5
提示:
其中:
- 链表中节点数目为 n
- 1 <= n <= 500
- 500 <= Node.val <= 500
- 1 <= left <= right <= n
解题思路:
拿个栈把区间内的元素一个一个存起来,然后再遍历一遍按出栈顺序给节点赋值,由栈的先入后出性质完成链表反转。
代码:
#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <stack>
using namespace std;
template <class Type> class ListNode {
public:
Type data;
ListNode<Type> *next;
};
class Solution {
public:
ListNode < int > *reverseBetween(ListNode<int> *head, int left, int right) {
ListNode<int> *cur = new ListNode<int>();
stack<int> s;
cur = head;
int i = 1;
while(cur != NULL) {
if(i >= left && i <= right) {
s.emplace(cur->data);
}
cur = cur->next;
i++;
}
cur = head;
i = 1;
while(cur != NULL) {
if(i >= left && i <= right) {
cur->data = s.top();
s.pop();
}
cur = cur->next;
i++;
}
return head;
}
};
时间复杂度O(n),空间复杂度O(1)。
下一篇:【2022小米秋招】笔试题2——二叉搜索树转换双向链表
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)