数据结构与算法 | Leetcode 206. Reverse Linked List

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

相关练习

参考资料

请我喝半杯☕️