206.Reverse-Linked-List

206. Reverse Linked List

题目地址

题目描述

Reverse a linked list.

代码

Approach 1: 使用while Iterative

  1. 1.
    保存next 节点
  2. 2.
    curr的next节点指向prev节点
  3. 3.
    prev保存curr节点
  4. 4.
    curr保存next节点
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
​
// prev => cur => next
while(curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
​
head = prev;
​
return head;
}
}

Approach #2 Recursive

n1 → … → nk-1 → nk → nk+1 ← … ← nm
Complexity analysis
  • Time complexity : O(_n). Assume that n is the list's length, the time complexity is O(n).
  • Space complexity : O(_n). The extra space comes from implicit stack space due to recursion. The recursion could go up to n_ levels deep.
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// head => next <= next.next <=
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}