The reverse of the single linked list is an easy level of the topic, the topic in the force buckle on the submission of 470,000 times, but also frequently appeared in the interview, it can be said is very popular, its brothers also follow the scene. This question itself is relatively simple, and its “mate” is not so simple. Today’s article starts with a simple analysis of single linked list reversals.

The problem is described as follows.

Inverts a single linked list.

Example:

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

Method one: double pointer iterationThe iterative method is to change the pointing of the list nodes one by one in the process of traversing the list. The key point is to change the pointing of the nodes while not causing the chain to be broken. We can use two variablespreandcurTo represent the currently accessed node and the previous nodecur.next = pre, 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;
        }
        returnpre; }}Copy the code

Complexity analysis

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

Recursion is a magical existence, so simple, and so complex, sometimes feel it is close, in fact, it is so far, sometimes feel to recognize it again, but it is still it, never changed. Every time you use recursion, you understand it a little bit more.

The recursion method to solve the list inversion lies in the assumption that the list has been inverted other nodes, what to do with the current node. Let’s say the list is


N 1 – N 2 – . . . – N k – N k + 1 – . . . – N n N_1 \rightarrow N2 \rightarrow … \rightarrow N_k \rightarrow N_{k+1} \rightarrow … \rightarrow N_n

If the Nk+1N_{k+1}Nk+1 to NnN_nNn part has been inverted, then the structure of the list will look like this:


N 1 – N 2 – . . . – N k – N k + 1 please . . . please N n N_1 \rightarrow N2 \rightarrow … \rightarrow N_k \rightarrow N_{k+1} \leftarrow … \leftarrow N_n

In order to change the orientation of Nk+1N_{k+1}Nk+1 and NkN_kNk, do the following:


N k . n e x t . n e x t = 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;
        returnnode; }}Copy the code

List inversion using recursion, is a very amazing solution, but also not very easy to understand, the following with the help of animation slow recursive call process.

Complexity analysis

  • Time complexity:O(n).
  • Space complexity:O(n), using recursion, the stack depth of recursion isn.

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

  • Switch nodes in a linked list in pairs