前面我们实现了几种常见的 链表，接下来，我们来聊聊如何实现 单链表 的反转？
链表反转
Leetcode 206: Reverse Linked List
示例：
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Input: NULL
Output: NULL
我们可以通过循环遍历和递归这两种方式来实现链表的反转。
遍历
思路
定义三个指针，分别为 prev、curr、next，然后遍历所有 node 结点，并移动这三个指针，改变 curr 结点的 next 指向，指向 prev 结点，实现 linkedList 的反转。
代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode next = null;
while(curr != null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head = prev;
return head;
}
}
源码
递归
其实递归的实现方式和前面循环的方式非常相似，前者是通过循环来移动指针，后者是通过递归来移动指针。
定义一个递归接口，传入 curr 与 prev 节点作为参数，内部再将 curr 的作为下次递归调用的 prev 入参，curr.next 作为下次递归调用的 curr 入参。
代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {
public ListNode reverseList(ListNode head){
return reverseRecursively(head, null);
}
public ListNode reverseRecursively(ListNode curr, ListNode prev) {
if(curr == null){
return null;
}
if(curr.next == null){
ListNode head = curr;
curr.next = prev;
return head;
}
ListNode next1 = curr.next;
curr.next = prev;
ListNode head = reverseRecursively(next1, curr);
return head;
}
}
源码
这两种方式的时间复杂度均为 O(n)，空间复杂度均为 O(1)。
参考资料
《数据结构与算法之美》