在想这迭代和递归到底是怎么变换的,必须要理清楚指针。
迭代写法
图像理解:
206:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode *tail = head;
while(tail && tail->next)
{
ListNode* cur = tail->next;
ListNode* nxt = cur->next;
cur->next = dummy->next;
dummy->next = cur;
tail->next = nxt;
}
return dummy->next;
}
};
92:
/**
* 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);
dummy->next = head;
ListNode* front = dummy;
for(int i = 1; i < m; i++)
front = front->next;
ListNode* tail = front->next;
for(int i = m + 1; i<= n; i++)
{
ListNode* cur = tail->next;
ListNode* nxt = cur->next;
cur->next = front->next;
front->next = cur;
tail->next = nxt;
}
return dummy->next;
}
};
递归
图解:
206:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return p;
}
};
92:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
ListNode* tail;
ListNode* dfs(ListNode* head, int cnt)
{
tail = head->next;
if(cnt == 1) return head;
ListNode* p = dfs(head->next, cnt - 1);
head->next->next = head;
head->next = tail;
return p;
}
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(!head) return nullptr;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* front = dummy;
for(int i = 1; i < m; i++)
front = front->next;
front->next = dfs(front->next, n - m + 1);
return dummy->next;
}
};