Subject to introduce

Buckle 206: leetcode-cn.com/problems/re…

Method 1: iteration

Suppose the linked list is 1→2→3→∅, we want to change it to ∅←1←2←3.

When traversing the list, change the next pointer of the current node to point to the previous node. Because a node does not reference its previous node, it must store its previous node first. The latter node also needs to be stored before the reference can be changed. Finally, the new header reference is returned.

The code is as follows:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr ! =null) {
            // Save the next node of cur in advance
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        returnprev; }}Copy the code

Complexity analysis

• Time complexity: O(n), where n is the length of the list. You need to traverse the list once.
• Space complexity: O(1).

Method two: recursion

The code is as follows:

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;
        returnnewHead; }}Copy the code

Complexity analysis

• Time complexity: O(n), where n is the length of the list. You need to reverse each node of the linked list.

• Spatial complexity: O(n), where n is the length of the linked list. The spatial complexity depends primarily on the stack space of recursive calls, which is at most N layers.