Back to a frequently asked question in the interview: Single-linked List Inversion, it is not so easy to mention the “friends”. Today, let’s analyze its second brother: “exchange the nodes in the linked list in pairs.”

And they describe it as follows.

Given a linked list, swap the adjacent nodes in pairs and return the swapped linked list.

You can’t just change the value inside the node, you need to actually swap nodes.

Example: Given 1->2->3->4, you should return 2->1->4->3.

Method 1: three pointer iteration

With the last single list inversion of the basis of the double pointer iteration method, and then to solve its second brother, it is relatively easy a lot.

“A skillful woman cannot make bricks without straw.” If there are two nodes left to swap, then there must be two nodes to swap. If there are two nodes left to swap, then there must be two nodes left to swap.

We can use two variablesfirstandsecondTo represent the first and second nodes to be swapped currently.



As shown in the figure above, after the swap,2ndThe node to1stNode, and1stNodes can no longer point to2ndNode, otherwise you form a ring. Should let1stThe node to2ndThe original node is the next node, so we need to put it first2ndThe next node of the original node is recorded.

The exchange operation pseudocode is as follows:

ListNode third = second.next;
second.next = first;
first.next = third;

At the same time, want to consider the following this kind of scenario, nodes 1 and 2 has been completed, now it is up to the exchange of node 3 and 4, to ensure the node 3 and 4 after the exchange, node 1 4 points to the node, so need to record each round of exchange of the precursors of node, below this example is the precursor node 1.



The last header pointer to be returned is the second node in the first round of switching.

The animation is shown below.

class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode pre = null, first = head, second = head.next; ListNode ans = second; while (first ! = null && second ! = null) { ListNode third = second.next; second.next = first; first.next = third; // If (pre! = null) { pre.next = second; } pre = first; // 1st, 2nd first = third; second = (first ! = null) ? first.next : null; } return ans; }}

Complexity analysis

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

When I was talking about recursion last time, I wrote a little bit of my own insight about recursion, and I can’t resist writing it again.

Recursion is a magical existence, so simple, so complex, sometimes it feels very close, in fact it is so far, sometimes it feels like a new understanding of it, but it is the same, never changed. Every time I use recursion, I understand it a little bit better.

If swapping two nodes is considered a turn, then all the nodes in the pair-swapping list are made up of many such turns. Recursion is done backwards, which means that when we swap the current turn, we can assume that the future turn has already completed.

As shown in the schematic diagram below, also take the linked list1->2->3->4->5->nullFor example, when switching between node 1 and node 2, suppose3->4->5->nullThe swap has been completed and node 1 points toswapPairs(3)Nodes returned:



The code is as follows:

class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode first = head, second = head.next; first.next = swapPairs(second.next); second.next = first; return second; }}

Complexity analysis

  • Time complexity:O(n).
  • Space complexity:O(n), recursion is used, and the recursion stack depth isn.

Next episode, the “big brother” of single linked list inversion:

  • K in a group of flipped lists