leetcode_reverse_linked_list_ii

发表于

难度：Medium

解题思路：找到要翻转区域的起始节点、结束节点和起始节点之前的节点。然后开始翻转。

代码如下：

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
/**
 * 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) {
        ListNode *dummy = new ListNode(-1), *pre_first = dummy, *first = dummy, *second = dummy;
        dummy->next = head;
        int i;
        for(i = 1; i < m; i++)
            pre_first = pre_first->next;
        first = pre_first->next;
        second = first;
        for(; i < n; i++)
            second = second->next;
        
        pre_first->next = second;
        pre_first = second->next;

        for(int j = m; j <= n; j++)
        {
            ListNode *first_next = first->next;
            first->next = pre_first;
            pre_first = first;
            first = first_next;
        }
        return dummy->next;
    }
};

运行时间：3ms，超过5.12%