Reverse Linked List 2 

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
/**
 * 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** s = &head;
      ListNode *a = nullptr, *b = nullptr;
      int i = 1;
      while (i < m - 1) {
        s = &((*s)->next);
        i++;
      }
      a = *s;
      b = (*s)->next;

      while (i < n) {
        i++;
        ListNode *tmp = b;
        b = b->next;
        tmp->next = a;
        a = tmp;
      }

      (*s)->next->next = b;
      (*s)->next = a;

      return head;

    }
};

This fails for input [5], 1, 1 since we always blindly try to do the reversal operations.

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
      ListNode** s = &head;
      ListNode *a = nullptr, *b = nullptr;
      int i = 1;
      while (i < m - 1) {
        if (*s) {
          s = &((*s)->next);

        }
        i++;
      }
      a = *s;
      if (*s) {
        b = (*s)->next;
      }

      while (i < n) {
        i++;
        ListNode *tmp = b;
        if (b) b = b->next;
        if (tmp) tmp->next = a;
        a = tmp;
      }

      // always null check before deref
      if (*s && (*s)->next) {
        (*s)->next->next = b;
        (*s)->next = a;
      }

      return head;

    }
};

This fails when we have `[3,5], 1, 2`.

We never reverse it.

# Accepted Solution
```cpp
/**
 * 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** s = &head;
      ListNode *a = nullptr, *b = nullptr;
      int i = 1;
      if (m < n) {
          while (i < m ) {
            if (*s) {
              s = &((*s)->next);
            }
            i++;
          }
          a = *s;
          if (*s) {
            b = (*s)->next;
          }

          while (i < n) {
            i++;
            ListNode *tmp = b;
            b = b->next;
            tmp->next = a;
            a = tmp;
          }


          // always null check before deref
          if (*s && (*s)->next) {
            (*s)->next = b;
            *s = a;
          }
      }

      return head;

    }
};

Illustrated Explanations

Example 1

Example 2