pexels-photo-356807

前面我们实现了几种常见的 链表 ，接下来，我们来聊聊如何实现 单链表 的反转。

链表反转

Leetcode 206: Reverse Linked List

示例：

1
2
3
4
5
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 的反转。

LinkedList-Reverse-Iteratively

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 入参。

代码实现

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
/**
 * 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)。

相关练习

参考资料