---
description: Today 1 leet , tomorrow 頂天leet地
image: https://leetcode.com/static/images/LeetCode_Sharing.png
---
# Reverse Linked List II
[題目網址<i class="fa fa-link"></i>](https://leetcode.com/problems/reverse-linked-list-ii/)
## 題目敘述
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.

:::spoiler **Example 1**

> **Input:** head = [1,2,3,4,5], left = 2, right = 4
> **Output:** [1,4,3,2,5]
:::

:::spoiler **Example 2**
> **Input:** head = [5], left = 1, right = 1
> **Output:** [5]
:::

## 解題思維
將陣列分為三等分l,m,r，並新增一個指向head的指標，以stack存取m的元素將其反轉，
重新連接l-m-r。
以範例1為例:
1.分為三等份l,m,r
[`1`, `2,3,4`, `5`]
2.反轉m
[`1`, `4,3,2`, `5`]

## 程式碼

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *h=new ListNode(),*l,*m,*r;
        stack<ListNode*> s;
        int index=0;
        h->next=head;
        l=h;
        while(index<left-1)
        {
            l=l->next;
            index++;
        }
        m=l;
        while(index<right)
        {
            s.push(m->next);
            index++;
            m=m->next;
        }
        r=m->next;
        if(!s.empty())
        {
            l->next=s.top();
            l=l->next;
            s.pop();
            while(!s.empty())
            {
                l->next=s.top();
                l=l->next;
                s.pop();
            }
            l->next=r;
        }
       return h->next;
    }
};

$O(n)$

###### tags: `LeetCode` `Linked List`