A sequence.

As a basic data structure, linked lists are simple to understand. It uses Pointers, or references, to concatenate a set of discrete memory Spaces (nodes) to form a data storage structure.

Linked lists can be divided into single linked lists, bidirectional linked lists, cyclic linked lists and bidirectional cyclic linked lists according to the pointing and richness of their Pointers. The difference is whether to add richer Pointers to nodes on the basis of a single linked list, so that it can achieve richer functions.

Although linked lists are easy to understand, the code of linked lists is not so easy to write, especially for some operations on single lists, such as list inversion, list double inversion, ordered list merge and so on.

You can try it yourself. Put down your phone, pick up a pen and paper, and conduct a mock interview, just making a single linked list and turning it in reverse and seeing if you can pass it all at once.

When writing the linked list code, it is easy to lose the pointer and cause the linked list to break. So when we’re working with linked lists, the order of operations is what we care about.

Although linked list code is not easy to write, linked list is a frequent interview, some common algorithm implementation, we developers must master.

If you want to reverse a list in pairs, you can reverse it in pairs. If you want to reverse a list in pairs, you can reverse it in pairs.

Single – linked lists are reversed in pairs

2.1 What is pairwise inversion of a single linked list?

Single list inversion is easier to understand, it is the reverse order, but what does double inversion mean?

We know that a singly linked list is a data structure that is connected by Pointers, one node at a time. So we take these nodes, two of them, and we reverse them in pairs.

This kind of problem of double reverse of single linked list is very suitable to solve with the idea of recursion, each step operation is enclosed in a small unit, and then repeat the operation.

In general what recursion can do, a loop can do, so let’s just do these two solutions separately.

2.2 Cyclic solution

Regardless of the use of loops or recursion, in fact, it is to disassemble the steps of linked list node exchange and put them in a small loop (recursion) to deal with. Compared with recursion, the circular method is clearer in the use of nodes, so we take the circular method as a starting point.

Recursion, or looping, is all about finding an abstract model and repeating the same thing over and over again at each invocation step.

In pairwise inversion of a singly linked list, it looks like you’re dealing with two nodes, but you’re actually dealing with a relationship between four nodes.

In addition to the nodes A and B to be reversed, it is also necessary to operate the precursor node PREv of A and the Next node B-next of B.

Every time we reverse, we’re actually operating on these four nodes, and the operation is very important.

As shown in the figure, the operation of step ① has two steps. Since the Pointers of the operation do not affect each other, the code is written in no order. After ensuring that the Pointers of prev and B-next are pointing correctly, the inversion of node A and node B can be started, namely step ②.

Finally, we just need to move forward the node we care about to enter the next loop.

In this step, we’re manipulating Pointers to four nodes, but each time we start, there are only prev nodes that are the precursor of A. To keep things consistent throughout the loop, we can add a virtual header to the list to help us simplify our code.

At this point, the steps are clear, reversing the nodes two at a time and moving the dummy pointer forward.

And then finally, we need to pay attention to some boundary conditions, pay attention to when our loop stops.

In the scenario of double inversion of a single linked list, the number of nodes in the linked list is either single or double. When the number of nodes is singular, the last node can not find the node that can be reversed and swapped, so it can remain unchanged.

The next step is to go straight to the loop code, which we are familiar with using Java code to achieve.

public ListNode swapPairs(ListNode head){

  // add dummy to the list header

  ListNode dummy = new ListNode(-1);

  dummy.next = head;

  head = dummy;

  // Loop exit condition, pay attention to the linked list node number is odd or even

  while(head.next ! =null&& head.next.next ! =null) {

    // Start the reverse

    ListNode a = head.next;

    ListNode b = a.next;

    head.next = b; / / steps (1)

    a.next = b.next; / / steps (1)

    b.next = a; / / step (2)

    // dummy pointer moves forward

    head = a;

  }

  return dummy.next;

}

Copy the code

Insert dummy into the head of the list and start the loop. The loop exits when the end of the list is reached. Note that the number of nodes is single or double. Then follow the steps illustrated in the previous article, start to operate the linked list pointer to reverse it in pairs, and finally move the dummy pointer forward.

2.3 Recursive solution

The recursive solution, compared to the circular solution, has a lot less code and looks cleaner. Mainly because of the recursion, through the layer upon layer of calls, we’re storing some variables on the method stack that we’re going to operate on.

Here, in recursion, we still focus on three problems, trivial problems solved recursively, termination conditions, and return values.

Recursively, it’s easier to look at the code.

public ListNode swapPairs(ListNode head) {

  if (head == null || head.next == null) {

    return head;

  }

  ListNode next = head.next;

  head.next = swapPairs(next.next);

  next.next = head;

  return next;

}

Copy the code

Combined with a diagram of the previous steps.

The recursive method is more complicated. Combining with the above figure, we can find the idea that the loop is a front-to-back movement of the operation window, while the recursion is a back-to-front movement of the operation window. Note the recursive termination condition and the rotation of the node pointer each time the recursive operation is performed.

Three. Summary moment

Here is the pairwise inversion of single – linked lists, on the end of the explanation.

Write linked list code, in addition to test logical thinking ability, but also test coding ability, write more practice is the core.

Note the boundary conditions and the swap rotation of node Pointers in each operation unit. The operation sequence of each step is explained clearly in a graphic way. If you have any questions, please leave a comment.

Did this article help you? Message, forward, favorites is the biggest support, thank you!

“Growth”, will get the learning materials I prepared.