# Algorithm learning: linked list inversion

2022-01-26 22:24:10 Yan Long

## subject 1：

The recursive method ：

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
}

return last;

}
};```

Iterative method ：

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:

ListNode* ret = nullptr;

ListNode* tmp;
while(current != nullptr) {
tmp = current->next;

current->next = ret;
ret = current;

current = tmp;

}

return ret;
}
};```

## subject 2：

subject ： Give you the head pointer of the single linked list head And two integers left and right , among left <= right . Please reverse from position left To the position right The linked list node of , return Inverted list .

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:

ListNode* successor = nullptr;

ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
}

ListNode* last = reverseN(head->next, n -1);

return last;
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
if(left == 1) {
}

}
};```

## summary

The idea of recursion is compared with iteration , It will be a little difficult to understand . The time complexity of recursion and iteration is o(n), But the space complexity of iteration is only o(1). The technique of recursive processing is ： Don't jump into recursion , Instead, it uses clear definitions to implement algorithmic logic .