7-8 lines C++ / Python / Ruby

• Three different implementations of the same algorithm, taking advantage of different strengths of the three languages. I suggest reading all three, even if you don't know all three languages.

All three of course work swap the current node with the next node by rearranging pointers, then move on to the next pair, and repeat until the end of the list.

C++

Pointer-pointer `pp` points to the pointer to the current node. So at first, `pp` points to `head`, and later it points to the `next` field of ListNodes. Additionally, for convenience and clarity, pointers `a` and `b` point to the current node and the next node.

We need to go from `*pp == a -> b -> (b->next)` to `*pp == b -> a -> (b->next)`. The first three lines inside the loop do that, setting those three pointers (from right to left). The fourth line moves `pp` to the next pair.

``````ListNode* swapPairs(ListNode* head) {
ListNode **pp = &head, *a, *b;
while ((a = *pp) && (b = a->next)) {
a->next = b->next;
b->next = a;
*pp = b;
pp = &(a->next);
}
}
``````

Python

Here, `pre` is the previous node. Since the head doesn't have a previous node, I just use `self` instead. Again, `a` is the current node and `b` is the next node.

To go from `pre -> a -> b -> b.next` to `pre -> b -> a -> b.next`, we need to change those three references. Instead of thinking about in what order I change them, I just change all three at once.

``````def swapPairs(self, head):
while pre.next and pre.next.next:
a = pre.next
b = a.next
pre.next, b.next, a.next = b, a, b.next
pre = a
return self.next
``````

Ruby

Again, `pre` is the previous node, but here I create a dummy as previous node of the head. And again, `a` is the current node and `b` is the next node. This time I go one node further and call it `c`.

To go from `pre -> a -> b -> c` to `pre -> b -> a -> c`, we need to change those three references. Here I chain the assignments, pretty much directly saying "`pre` points to `b`, which points to `a`, which points to `c`".

``````def swap_pairs(head)
pre = dummy = ListNode.new 0
while a = pre.next and b = a.next
c = b.next
((pre.next = b).next = a).next = c
pre = a
end
dummy.next
end``````

• based on your python approach, python solution could be like this

``````  class Solution:
# @return {ListNode}
prev = self
while prev.next and prev.next.next:
prev.next, prev.next.next, prev.next.next.next = prev.next.next, prev.next, prev.next.next.next
prev = prev.next.next
return self.next``````

• Ha, yeah, although that line is quite long and I hate it when I have to scroll and can't see the whole code at once. So I'd break it:

``````def swapPairs(self, head):
while pre.next and pre.next.next:
pre.next, pre.next.next, pre.next.next.next = \
pre.next.next, pre.next, pre.next.next.next
pre = pre.next.next
return self.next
``````

But I do like the simplicity, not having extra variables whose meaning I need to remember. Just explicity talking about the next three nodes. Verbose but neat.

• Those two lines within the while loop can also be written as:

``````pre.next, pre.next.next, pre.next.next.next, pre =\
pre.next.next, pre.next, pre.next.next.next, pre.next
``````

If only there's a way to simplify all these .next...

Here is a recursive version just for reference:

``````def swapPairs(self, head):

• Yeah, I had considered to merge the two lines, but I found it long enough already :-). And it would be mixing two really separate issues, doing the swap and moving forward.

But if we do mix them, let's go further and assign `pre` earlier so we can save two `.next`:

``````pre.next, pre, pre.next.next, pre.next = \
pre.next.next, pre.next, pre.next, pre.next.next.next
``````

Nice recursive one. I hadn't really tried because of the constant space requirement. It can similiarly be "optimized" a bit further:

``````head.next, head, head.next = \
``````

• I had a smile on my face when I see you shaved off 2 .next in the first one and 1 .next in the second one. Good job as always.

• In python solution, you use `self` instead `dummy` which most people use,it is very nice! i get it.

• In python solution, is self.next = head ?
Why you can return self.next without claiming self.next = pre.next at the beginning?

• ``````struct ListNode* swapPairs(struct ListNode* head) {
}
struct ListNode *current;

while((current = *linkp) != NULL && current->next){
current->next = current->next->next;
}

}
``````

Same as mine, your c code, but you provide three methods, brilliant!!!

• @swengzju My first line does set `pre = self` and then `pre.next = head` (which is equivalent to `self.next = head`, as `pre` and `self` are the same object).

• Hi Stefan, would you please explain what these two lines are doing? Sorry I don't really know how pointer to pointer works.
*pp = b;
pp = &(a->next);

• Very elegant python solution. However, can i ask why we can assign prev to self? And why self has "next" attribute in it? Thanks!

• Thanks! Why we can just swap the objects without considering the order (in Python)? I thought it would mess up the node's `next` properties.

• We need to go from *pp == a -> b -> (b->next) to *pp == b -> a -> (b->next).

Where in the code does a->next get set to the next swapped pair head? (i.e. in 1->2->3->4 and solution 2->1->4->3, where does 1->4 occur?)

• @erica76 Here is an example to show you the first iteration of the while loop.
Visualize the linked list as node_a->node_b->node_c->...etc....
In the first iteration, pp is a pointer to the pointer named head and head is a pointer to the first node in the linked list.

So, in first iteration, *pp = b; is changing pp->head->node_a to
pp->head->node_b (after you swap node_a, node_b you must change head to point to node_b)

In first iteration, pp = &(a->next); is then moving pointer pp from pointing pointer head to point to the address where node_c is stored.
(visualize linked list head->node_b->node_a->node_c->.... and pointer pp was changed to be pp->node_c in order to set up the swap between node_c->node_d in the second iteration)
Cheers!
Zach

• This post is deleted!

• hello, I have a question, when I wrote the code as:pre.next, b.next, a.next = b, a, b.next in one line,it accepted.
but when I wrote the code as:pre.next=a
b.next=a
a.next=b.next it TLE,how coulde it happend?why?

• @rawmy12 When you do `pre.next, b.next, a.next = b, a, b.next`, Python first evaluates the tuple on the right side and then assigns it to the left side targets. So `a.next` becomes what `b.next` was before that line. That's not the case in your separate-lines version, because when you assign to `a.next`, you already changed `b.next`. It's not anymore the value it was before.

• @StefanPochmann I got it.Maybe it's one of the Python's advantages to other programming languages. Am I right :-D

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.