Like first, look later, make it a habit!

I have recently written several articles on “linked lists”, both theoretical and manual. In fact, in the actual development, you will rarely implement linked lists yourself. The purpose of these articles is also to deepen the understanding of linked lists as data structures.

Today we’re going to get down to business and talk about the list questions you might be asked in an interview. For this article, I consulted several recent job changers. One of the most frequently asked interview questions was: “The reverse of a one-way linked list!” So today we’re going to talk about reversing one-way lists.

What is an inverted one-way list

In fact, the so-called reverse one-way linked list is to change the original order of “A->B->C->D” into “D->C->B->A”. This operation is called reversing a one-way linked list.

Implementation approach

The idea is to create a new linked list, one node at a time from the one-way list to be reversed, and put it behind the head node of the new list.

Code implementation

/** * reverse single linked list **@paramHead The head node of the linked list */
public void reversetSingleLinkedList(Node head) {
    // Check whether the list is empty or has only one node
    if(head.next == null || head.next.next == null) {return;
    }
    // Define auxiliary variables to be used by traversing the list.
    Node cur = head.next;
    // Hold the next node of the secondary node (cur).
    Node next = null;
    // Create a header node (for reverse list use)
    Node reverseHead = new Node("reverseHead");
    // Iterate over the list to be reversed
    while(cur ! =null) {// Save the next node of the secondary node (cur)
      next = cur.next;
      // Point the pointer field of the secondary node (to the next node) to the next node of the reverseHead.
      cur.next = reverseHead.next;
      // Set the pointer field of the reverseHead (pointing to the next node) to cur
      reverseHead.next = cur;
      // Move the auxiliary variable back
      cur = next;
    }
    // Place the pointer field of the next node in the list head node to be reversed to the next node in the list head node
    head.next = reverseHead.next;
}
Copy the code

The code on

The first step:

cur.next = reverseHead.next;
reverseHead.next = cur;
Copy the code

The first line of code means that the pointer field to the auxiliary variable (cur) that will be used for traversal each time through the loop points to the next node in the newly created reverseHead. To obtain a node from the list to be reversed, and put this node before the next node of the reverseHead. Combined with the second line of code (reversehead.next = cur), you get one node at a time from the list to be reversed and place it behind the reverseHead.

The second step:

head.next = reverseHead.next;
Copy the code

When the loop ends, the structure of the reverseHead is an inverted linked list. By replacing the reverseHead head node, the pointer field of the head node in the list to be reversed points to reverseHead. Next (the next node of the head node in the list to be reversed), so as to realize the reversal of the single-linked list.

conclusion

Through the above way can easily achieve the reverse of the single linked list, is not afraid of the interviewer questions? If you don’t understand anything or have problems with your writing, feel free to comment in the comments section.

Today’s share is here first, read all read, click a “like” and then go!