Recursion properties in linked lists

These reviews

1. Detailed analysis of dynamic array data structure implementation process (Java implementation)
2. Detailed analysis of stack and queue data structure implementation process (Java implementation)
3. Detailed analysis of linked list data structure implementation process (Java implementation)

preface

In the previous implementation of linked list data structure, the implementation process of linked list data structure has been fully understood. But for linked lists, it’s actually related to recursion. Although recursion is generally used in tree data structures, it is very convenient to use recursion in tree structures. It is also possible to use recursion in linked lists because they are inherently recursive, but lists are linear structures that can be easily implemented using non-recursive methods, so most of the time they are implemented in a circular manner. But if you use recursion in linked lists, it helps to lay a foundation for recursion so that you can understand more about data structures like trees and recursive algorithms later on, which is very helpful. Therefore, we can use a problem about linked lists in LeetCode to solve it recursively, so as to achieve the purpose of understanding the recursive nature of linked lists.

A problem with linked lists in LeetCode

Item 203 removes a linked list element

Title description:

Deletes all nodes in the linked list that are equal to the given value val. Example: Input: 1->2->6->3->4->5->6, val = 6 output: 1->2->3->4->5 Source: LeetCode link: https://leetcode-cn.com/problems/remove-linked-list-elements Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

The linked list node class provided by the topic:

/** * Definition for singly-linked list. */
public class ListNode {
    int val;
    ListNode next;
    ListNode(intx) { val = x; }}Copy the code

Directions: For this part, you are allowed 30 minutes to answer the question.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode removeElements(ListNode head, int val) {}}Copy the code

For this problem, you can review the deletion logic of linked lists by trying to use a non-recursive approach and then implementing it with and without virtual head nodes.

Non-recursive mode and no virtual head node

1. If you do not use a virtual header, you can first determine directly whether head is not null and whether its value is the element to be deleted, and if so, delete the current head node. It is important to note that there may be multiple elements to be deleted piled at the head of the list or the entire list of elements to be deleted, so we can use the while loop to determine when to delete the first node in the list.

2. After dealing with the head part, just need to delete the elements in the middle of processing, review the list of deleted logic, need to find the lead node to node is to be deleted, so head start with the head of the list at nodes, as the first front nodes prev (because the head has been processed, did not want to delete the element). The while loop is used to determine whether the next node of the prev needs to be deleted until all the elements to be deleted are deleted.

3. Finally, return the head node head to obtain the linked list of deleted elements.

The above ideas are realized as follows:

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // A non-recursive solution that does not use virtual headers
        // Delete the elements that need to be deleted at the beginning of the list
        while(head ! =null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }

        // If head == null, all elements in the list need to be deleted
        if (head == null) {
            return null;
        }

        // Process the elements that need to be deleted in the middle of the list
        ListNode prev = head;
        // See if the next element in the prev needs to be deleted each time
        while(prev.next ! =null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            } else{ prev = prev.next; }}returnhead; }}Copy the code

Submission Results:

Then use the virtual header to implement this problem, the idea is as follows:

1. Create a virtual head node and point to the head node of the list.

2. At this point, all the elements in the whole list have a front node, and the element to be deleted can be uniformly deleted through the front node. At this point, the virtual head node is used as the first front node prev. The while loop is used to determine whether the next node of the prev needs to be deleted until all the elements to be deleted are deleted.

3. Finally, return the next node of the virtual head node, head.

The above ideas are realized as follows:

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // A non-recursive solution using virtual headers
        // Create a virtual head node
        ListNode dummyHead = new ListNode(-999);
        dummyHead.next = head;

        // Process the elements in the linked list that need to be deleted
        ListNode prev = dummyHead;
        // See if the next element in the prev needs to be deleted each time
        while(prev.next ! =null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            } else{ prev = prev.next; }}// Return the list head node
        returndummyHead.next; }}Copy the code

Submission Results:

At this point, both schemes work correctly. For the logic of the deletion in the use of virtual nodes and without the use of virtual node is implemented again, this is also in the previous list data structure involved in the implementation of the part, here again to review it again to deepen impression, also convenient behind use recursive way to realize the subject after comparing the similarities and differences of two different ways.

Basic concepts and examples of recursion

Recursion, essentially, is to take the original problem, turn it into a smaller problem, until it becomes a basic problem and solves the basic problem, and then step by step return the result to solve the original problem.

Take an example: array summation.

As you can see from the diagram, recursion is actually reducing the size of the original problem step by step, until the basic problem appears and then you solve the basic problem and then you go back up to the basic solution and then you solve the solution of each scale until you solve the original problem.

The above process is coded as follows:

/** * array summation recursion example **@authorSnow's looking for mei *@date2020/2/8-10:30 * /
public class Sum {
    /** * add to array **@paramArray Array of sums *@returnReturns the sum */
    public static int sum(int[] array) {
        // Computes the sum of all numbers in array[0...n]
        return sum(array, 0);
    }

    /** * computes the sum ** of all numbers in array[l...n]@paramArray Array of sums *@paramL Left margin *@returnReturns the sum */
    private static int sum(int[] array, int l) {
        // Basic problem: Return 0 if the array is empty
        if (l == array.length) {
            return 0;
        }
        // Turn the original problem into a minor problem
        return array[l] + sum(array, l + 1);
    }

    /** * test array summation */
    public static void main(String[] args) {
        int[] nums = {1.2.3.4.5.6.7.8}; System.out.println(sum(nums)); }}Copy the code

Running results:

For the above example, it is important to note the “macro” semantics of recursive functions when using recursion. In the example above, “macro” means calculating the sum of all the numbers in the array[L…n] range. Like this understanding recursive functions to watch in the function to convert the original problem into a small problem, will better understand the function of things to do, simple recursive functions is a complete function of a function, just call yourself, every time into a small problem when complete function is an array of a certain number, plus the number of remaining and, until a myriad of additive. The recursive process for the array sum is shown below:

It can also be represented as follows. The code in the following figure is the split code to make it easier to show the process:

Now that you know the basic concepts and flow of recursion, it’s time to look at the natural recursion properties of linked lists.

Linked lists are inherently recursive

A linked list is essentially a chain of nodes. It looks like this:

In fact, linked lists can also be understood by recursion as consisting of a head node followed by a shorter list. It looks like this:

For a shorter list in the figure above, which is also formed by a head node attached to a shorter list, and so on until NULL, which is actually a linked list, is the basic problem of recursive linked lists.

So let’s go back to item 203: Removing a linked list element. The linked list provided by the topic can be regarded as the structure shown in the above figure, and then use recursion to solve the elements to be deleted in the smaller linked list to obtain the solution of the small problem, and then see whether the head node needs to be deleted. If it does, the solution of the small problem will be returned, which is the solution of the original problem. If you don’t delete it, you combine the head node with the solution of the small problem and go back to get the solution of the original problem. This process is illustrated by the following diagram:

The code implementation is as follows:

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Use recursion to remove elements from the list
        // Build basic problem, return null if linked list is empty
        if (head == null) {
            return null;
        }

        // Build a small problem: get the solution to a smaller list that hangs after the head node
        ListNode result = removeElements(head.next, val);
        // Determine whether the head node needs to be deleted, and combine the small problem solution to get the original problem solution
        if (head.val == val) {
            // The header node needs to be deleted
            return result;
        } else {
            // The head node does not need to be deleted, and the solution of the small problem is combined to get the original solution
            head.next = result;
            returnhead; }}}Copy the code

Submission Results:

You can verify from the commit results that the implementation logic is error-free. The code can also be simplified as follows:

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Use recursion to remove elements from the list
        // Build basic problem, return null if linked list is empty
        if (head == null) {
            return null;
        }

        // Build the small problem: get the solution to the smaller linked list that hangs after the head node, and then hangs after the head node
        head.next = removeElements(head.next, val);
        // Determine whether the head node needs to be deleted, and combine the small problem solution to get the original problem solution
        returnhead.val == val ? head.next : head; }}Copy the code

Submission Results:

At this time, compared with the previous non-recursive way to achieve the solution, we can find that the use of recursive way to achieve is very elegant, the code is very simple and easy to read. Let’s look at how this recursion works. The recursive running process is shown in the figure below:

At this point, the recursive process of this topic is finished. For the above process, it is the step by step call of the sub-process. After the call, the sub-process calculates the result, and then returns the result step by step to the upper level call, and finally gets the result. The node deletion occurs on line 6, where the solution of the smaller problem is solved and the current call is organized to form the solution of the current problem.

At the same time, it is important to note that recursive calls come at a cost, both in terms of function calls and the use of system stack space. There is some time overhead when a function is called, including the need to record where the current function is executed, what local variables are in the function, and so on, and then push that state onto the system stack. However, in the process of recursive calls, the stack space is consumed, so for recursive functions, if the basic problem is not addressed, the recursive function will continue to execute until the stack space is used up. At the same time if you use a recursive process of the great amount of data, are also likely to be using the system stack space, such as the above array sum if millions summation level, must level data system of stack space is not enough to use, remove elements in the chain table, if the list is too long system stack space is not enough. So be careful here.

All in all, it is relatively easy to write program logic recursively, and this feature is evident in nonlinear structures such as trees and graphs.

summary

At this point, the recursion and recursive nature in the list after using the example of an array sum and a title in the LeetCode example to do the corresponding process analysis have fully understanding, also found that the use of recursion writing logic is very simple and easy to read, compared to before the use of recursive way to realize the antithesis of the code, Recursive code is only a few lines long. However, recursion also has certain limitations. In the process of use, attention should be paid to the possession of system stack space. If the amount of data is too large, it is likely to burst the system stack space, so extra attention should be paid to this aspect.

---

If there is insufficient writing, please forgive me, please give more advice.

My personal blog website:www.xilikeli.cnWelcome to visit (#.#)

And welcome to mineMaking the home page, my personal blog has been open source, interested partners can dot star, thank you (#.#)