難度: Medium
類型: Linked List
前情題要:
反向連結 --- 給定一個連結的 list, 一個左邊位址, 一個右邊位置, 左邊位置小於或等於右邊位置, 把這個連結的左邊位置到右邊位置的連結反向, 回傳結果。(能夠一輪就給答案嗎?)
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Constraints:
- The number of nodes in the list is
n.
1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
思考方式:
stack 的先進後出特性, 剛好拿來做反向連結。
1. 為了不破壞原有的 link list, 所有 output link list 的成員都是 new 出來的。這種方式會花費比較多的記憶體空間。其實也有另一種方法是直接改在原本的 linked list 上, 有機會另一篇文章再寫。
2. 運算過程中, 在大於等於左邊位置, 卻還仍小於右邊位置之前, 這些 linked list 的成員都 push 進Stack裡, 直到等於右邊位置時, 把右邊位置的 linked list 放上output連結後, 把 stack 裡的內容一個一個 pop 出來, 直到 stack 為空。
3. 記得更新 input linked list pointer 與 output linked list pointer。每次設定完一個新的output成員後, 記得把 output pointer 指定到 next。
結果:
Runtime: 0 ms, Beats: 100%
Memory: 11.24 MB, Beats: 38.10%
Accepted44 / 44 testcases passed
tendchen
submitted at Nov 07, 2025 05:39/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode *out=nullptr;
ListNode *cur_OutNode=nullptr;
ListNode *cur_InNode;
stack<ListNode> sListNode;
cur_InNode=head;
int i,j;
for (i=1;;i++)
{
if (cur_InNode==nullptr) return out;
if (i<left)
{
if (out==nullptr)
{
out=(new ListNode(cur_InNode->val));
cur_OutNode=out;
cur_InNode=cur_InNode->next;
}
else
{
cur_OutNode->next=(new ListNode(cur_InNode->val));
cur_OutNode=cur_OutNode->next;
cur_InNode=cur_InNode->next;
}
}
else
{
if (i<right)
{
sListNode.push(*cur_InNode);
cur_InNode=cur_InNode->next;
//cout << "push and then size=" << sListNode.size() << "\n";
}
else if (i==right)
{
if (out==nullptr)
{
out=(new ListNode(cur_InNode->val));
cur_OutNode=out;
cur_InNode=cur_InNode->next;
}
else
{
cur_OutNode->next=(new ListNode(cur_InNode->val));
cur_OutNode=cur_OutNode->next;
cur_InNode=cur_InNode->next;
}
for (j=1;;j++)
{
if (sListNode.size()==0) break;
cur_OutNode->next=(new ListNode(sListNode.top().val));
cur_OutNode=cur_OutNode->next;
sListNode.pop();
}
}
else
{
cur_OutNode->next=(new ListNode(cur_InNode->val));
cur_OutNode=cur_OutNode->next;
cur_InNode=cur_InNode->next;
}
}
}
}
};
