This is the sixth day of my participation in Gwen Challenge

Reverse a linked list

Topic describes

Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list.

Example 1:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

limit

  • 0 <= Number of nodes <= 5000

Thought analysis

List inversion problems we’ve encountered before, this time using a recursive solution, list plus recursion, in the algorithm these two kinds of problems are very difficult to write. The recursive solution method should first find the termination conditions of recursion, then decompose the big problems into small problems, and summarize the general rules of these problems.

Let’s consider the boundary problem first, and return if the list is empty.

ListNode newHead = reverseList(head.next); ListNode newHead = reverseList(head.next. Next = head; Next = null, and then returns the newHead after the inversion, which is newHead.

Keep recursing, because every recursion reverses with a 5, so the final return is newHead.

The code shown

Solution a: time complexity is O (n) 2 (2 ^ n)} {O O (2 n), and space complexity is O (1) (1)} {O O (1).

    public ListNode reverseList(ListNode head) { / / the 1-2-3-4-5

        if (head == null) {// Is null
            return head;
        }

        if (head.next == null) {return head;
        }
        ListNode newNode = reverseList(head.next);

        head.next.next = head;  //4.next.next = 4 5.next = 4
        head.next = null;
        return newNode;

    }
Copy the code

After the command is executed, a success message is displayed

Answer successful: Execution time :0 ms, beat 100.00% Java user memory consumption :38.4 MB, beat 17.56% Java usersCopy the code

summary

Recursion, there is first “recursion” and then “return”, “recursion” means that the problem is broken down into sub-problems to solve, sub-problems are broken down into sub-problems,… , until the disassembled sub-problem does not need to be disassembled into finer sub-problems (that is, it can be solved), “return” means that the smallest sub-problem is solved, then its upper sub-problems are solved, the upper sub-problems are solved, and the upper sub-problems are naturally solved,…. Until the original problem is solved.

Print the linked list from end to end

Topic describes

Enter the head node of a linked list and return the value of each node from end to end (as an array).

Example 1:

Input: head = [1,3,2] output: [2,3,1]Copy the code

limit

  • 0 <= List length <= 10000

Thought analysis

Printing the list from end to end, it’s easy to think of recursion, always determining if it’s tail, and if it’s not tail, move on to the next list. This type of problem is very easy to solve recursively. We also need a list to store the data in the linked list, and then put it into an array.

Of course, we can also use the stack to answer this problem, the use of the characteristics of the stack, first traversed the list into the stack, and then out of the stack, you can print the list from the end.

The code shown

Solution one: Time complexity is O(n){O(n)}O(n), space complexity is O(n){O(n)}O(n).

    List<Integer> list = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        recursion(head);
        int[] temp = new int[list.size()];
        for (int i = 0; i < list.size(); i++){ temp[i] = list.get(i); }return temp;
    }

    public void recursion(ListNode p){
        if (p == null) {return;
        }
        recursion(p.next);
        list.add(p.val);
    }
Copy the code

Solution two: traversing the linked list, using the characteristics of stack advanced after out, time complexity is O(n){O(n)}O(n), space complexity is O(n){O(n)}O(n).

    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        if (head == null) {return new int[0];
        }
        while(head ! =null){
            stack.push(head.val);
            head = head.next;
        }
        int size = stack.size();
        int[] arr = new int[size];
        int i = 0;
        while(! stack.isEmpty()){ arr[i++] = stack.pop(); }return arr;
    }
Copy the code

summary

It’s easy to think of a recursive solution to print the list from end to end, but we can also take advantage of the stack data structure to solve the problem.