LeetCode 206. 反转链表
迭代方法，先保存当前节点的 next 节点，再将当前节点的 next 指向前一个节点
// 迭代方法
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while(cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
/**
* 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 || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
复杂度分析
时间复杂度：O(n)。需要对链表的每个节点进行反转操作。
空间复杂度：O(n)。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
