博文中会简要介绍Leetcode P0206题目分析及解题思路。
“Reverse Linked List”是一道原型题，也是一道比较基础的链表问题。这道题有两种主流解法，一种是迭代的方式翻转链表，另一种是利用递归来翻转链表。
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLFollow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
首先介绍迭代的方式，利用迭代的思路比较直接。我们可以维护两个指针，一个是prev，另一个是curr，分别指向前一个元素和当前元素。每次翻转前，我们提前利用next变量保存curr的下一个元素，然后将curr指向prev，即可以完成翻转。接着我们将curr赋值给prev，将next赋值给curr，便可以迭代至下一轮翻转。
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null)
return head;
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
dummy.next.next = null;
dummy.next = prev;
return dummy.next;
}
}
下面是递归的解法。递归的解法的核心思路是先遍历到链表最深处，每次调用都传入两个指针，分别是prev和curr，即前一个元素的指针和当前元素的指针。在递归调用返回的时候，将curr指向prev即可。
以下是C++的题解代码实现。
/**
* Definition for singly-linked 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* reverseList(ListNode* head) {
this->_Reverse(nullptr, head);
return this->rhead;
}
private:
ListNode *rhead;
void _Reverse(ListNode *prev, ListNode *curr) {
if (!curr) {
this->rhead = prev;
return;
}
this->_Reverse(curr, curr->next);
curr->next = prev;
}
};