List inversion whole bucket (a) : animation detail single list inversion

The reversal of the single linked list is an EASY level topic, this topic in the force buckle on the submission of 470,000 times, but also frequently appeared in the interview, it can be said that is very popular, its brothers also followed the scene. The problem itself is relatively simple, and its “brothers” is not so simple. Today’s article starts with simplicity and examines the inversion of a single linked list.

And they describe it as follows.

Invert a single linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Method 1: Double pointer iteration

The iterative method is to change the direction of the nodes in the linked list one by one in the process of traversal. The key point is to avoid breaking the chain of the linked list while changing the direction of the nodes. We can use two variablespreandcurTo represent the currently accessed node and the previous nodecur.next = pre, in order to make the list continue to iterate forward, we also need to record the next node of the current node in advance, and assign the value of the next node tocurThe variable.

The animation is shown below.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode node = cur.next;
            cur.next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
}

Complexity analysis

• Time complexity:O(n).
• Space complexity:O(1).

Recursion is a magical existence, so simple, yet so complex, sometimes feel it is very close, in fact it is so far, sometimes feel a new understanding of it, but it is the same, never changed. Every time I use recursion, I understand it a little bit better.

Recursive method to solve the list inversion depends on the assumption that has reversed the list of other nodes, the current node how to deal with. Let’s say I have a linked list

$$ N_1 \rightarrow N2 \rightarrow … \rightarrow N_k \rightarrow N_{k+1} \rightarrow … \rightarrow N_n $$

If the $N_{k+1}$to $N_n$part has been reversed, the structure of the list looks like this:

$$ N_1 \rightarrow N2 \rightarrow … \rightarrow N_k \rightarrow N_{k+1} \leftarrow … \leftarrow N_n $$

$N_{k}$, $N_{k+1}$, $N_k$, $N_k$, $N_{k+1}$, $N_k$, $N_k$

$$ N_k.next.next = N_k $$

The code is as follows:

class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; }}

List inversion uses recursion, which is a pretty cool solution, but it’s also a little hard to understand, so let’s slow down the recursive process with the help of animation.

Complexity analysis

• Time complexity:O(n).
• Space complexity:O(n), recursion is used, and the recursion stack depth isn.

Next episode, the “second brother” of the single linked list inversion:

• Swap the nodes in the list in pairs