206.Reverse-Linked-List.md

206. Reverse Linked List

---

题目地址

https://leetcode.com/problems/reverse-linked-list/

https://www.jiuzhang.com/solutions/palindrome-partitioning-ii/

题目描述

Reverse a linked list.

代码

Approach 1: 使用while Iterative

1. 保存next 节点
2. curr的next节点指向prev节点
3. prev保存curr节点
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;
}