casyup.me@outlook.com

0%

leetcode/92ReverseLinkedListII

Posted on

Reverse Linked List II

给定一个单向链表, 按照距离 m, n 旋转单向链表

my solution (4ms, 100%)

其实这个题没什么好写的, 主要是这个题之前做过.

当时的代码量很大不说, 最后还没做出来…

old solution

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:
    int moth(ListNode* head, int m, int n) {
        if (m == n)
            return 1; // don't need replace

        return 0;
    }

    void replace_far() {
        pmptrv->next = pn;
        pm->next = pnnext;
        pnptrv->next = pm;
        pn->next = pmnext;
    }

    void replace_close() {
        pmptrv ? pmptrv->next = pn : nullptr;
        pm->next = pnnext;
        pn->next = pm;
    }

    void setpoint(ListNode* pcursor, int m, int n) {
        for (int i = 1; ; ++i) {
            if (i == m - 1) 
                pmptrv = pcursor;
            else if (i == m) 
                pm = pcursor;
            else if (i == m + 1) {
                pmnext = pcursor;
                if (i == n - 1)
                    pnptrv = pcursor;
                if (i == n)
                    pn = pcursor;
            }
            else if (i == n - 1)
                pnptrv = pcursor;
            else if (i == n) 
                pn = pcursor;
            else if (i == n + 1) 
                pnnext = pcursor;

            pcursor = pcursor->next;
            if (!pcursor)
                break;
        }
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (moth(head, m, n)) 
            return head;

        // ListNode* pcursor = head;
        setpoint(head, m, n);

        if (n - m >= 2)
            replace_far();
        else if (n - m == 1)
            replace_close();

        if (m == 1)
            return pn;

        return head;
    }

private:
    ListNode* pm = nullptr;
    ListNode* pn = nullptr;
    ListNode* pmptrv = nullptr;
    ListNode* pmnext = nullptr;
    ListNode* pnptrv = nullptr;
    ListNode* pnnext = nullptr;
};

… 天知道我 4 个月前脑子里面装的是什么, 会写出这样的代码.

关键是错了十几次, 然后还是没做出来…

new solution

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
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n || head == nullptr) 
            return head;

        ListNode temp(-1);
        temp.next = head;
        ListNode* p1 = &temp;
        ListNode* sta;
        int ax = 0;
        while (true) {
            if (++ax >= m) {
                sta = p1;
                p1 = p1->next;
                break;
            }

            p1 = p1->next;
        }

        ListNode* prev = p1;
        ListNode* cur = p1->next;
        ListNode* end = p1;
        while (ax++ < n) {
            ListNode* sav = cur->next;
            cur->next = prev;
            prev = cur;
            cur = sav;
        }

        sta->next = prev;
        end->next = cur;

        return temp.next;
    }
};

我采用了多放置一个头结点的方式来处理头结点也会被旋转的情况

先找到 m 的位置, 然后顺序旋转至 n 的位置, 最后将头尾衔接一下

最后的几次是我的尝试, 一开始的时候是 8ms, 但是我观察了 best solution, 发现区别不大

遂又尝试了一下, 然后是 4ms, 但是有时候不稳定, 总之在 4ms - 8ms 之间跳 (= =…)