206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
1.暴力解法
思路：
遍历要反转的链表，将每个元素依次插入一个新的链表的最前面即可完成反转
public static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
//用于测试用例
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
ListNode cur = this;
while (cur != null) {
res.append(cur.val + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = null;
while (head != null) {
ListNode node = new ListNode(head.val);
node.next = newHead;
newHead = node;
head = head.next;
}
return newHead;
}
复杂度分析：
时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n), 每次都要重新开辟空间去新建节点
-
2.迭代法
思路：
将当前节点的next指向前一个元素即可
image.png
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode p = cur.next;
cur.next = prev;
prev = cur;
cur = p;
}
return prev;
}
复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)
-
3.递归法
思路：
相当于每次先反转头节点之后的节点，反转完成之后在将头节点插入最后即可
image.png
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)，由于使用了递归，将会使用隐式栈空间，递归深度可能会达到n层
-
测试用例
public static void main(String[] args) {
int[] nums = new int[] {1, 2, 3};
ListNode head = new ListNode(nums);
System.out.println(head);
System.out.println("反转后的链表" + reverseList(head));
}
-
结果
1->2->3->4->5->NULL
反转后的链表5->4->3->2->1->NULL
-
源码
-
我会随时更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
