92. Reverse Linked List II

发表于 | 分类于

每日一题 2019 - 04 - 19

题目：

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

解法：

这个题让把链表中给定位置范围内的元素进行翻转，思路十分的简单，直接开辟一个 vector 用来存放[m,n] 范围内的元素，随后使用 reverse 函数将其翻转，最后再将其赋值回去即可；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        vector<int> now ;
        ListNode* temp = head ;
        int number = 1 ; 
        ListNode* before = NULL ;
        while( number < m)
        {
            temp = temp -> next ;
            number ++ ;
        }
        before = temp ;
        while( number <= n )
        {
            now.push_back(temp->val);
            temp = temp -> next ;
            number ++ ;
        }
        reverse(now.begin(),now.end());
        number = m ; 
        int i = 0 ; 
        while(number <= n)
        {
            before -> val = now[i];
            before = before -> next ;
            number ++ ;
            i ++ ;
        }
        return head ;
    }
};
0%
undefined