7-8 lines C++ / Python / Ruby


  • 73

    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);
        }
        return head;
    }
    

    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):
        pre, pre.next = 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
        pre.next = head
        while a = pre.next and b = a.next
            c = b.next
            ((pre.next = b).next = a).next = c
            pre = a
        end
        dummy.next
    end

  • 2
    C

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

      class Solution:
            # @param {ListNode} head
            # @return {ListNode}
            def swapPairs(self, head):
                prev = self
                prev.next = head
                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

  • 1

    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):
        pre, pre.next = 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.


  • 2
    T

    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):
        if head and head.next:
            head, head.next, head.next.next = \
                  head.next, head, self.swapPairs(head.next.next)
        return head

  • 0

    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 = \
          self.swapPairs(head.next.next), head.next, head, 
    

  • 0
    T

    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.


  • 0
    H

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


  • 0
    S

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


  • 0
    D
    struct ListNode* swapPairs(struct ListNode* head) {
        if(!head || !head->next){
            return head;
        }
        struct ListNode **linkp = &head;
        struct ListNode *current;
    
        while((current = *linkp) != NULL && current->next){
            *linkp = current->next;
            current->next = current->next->next;
            (*linkp)->next = current;
            linkp = &current->next;
        }
        return head;
    
    }
    

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


  • 1

    @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).


  • 1
    E

    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);


  • 3
    B

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


  • 1

    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.


  • 0
    S

    @StefanPochmann said in 7-8 lines C++ / Python / Ruby:

    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?)


  • 1

    @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.
    (visualize pp->head->node_a)

    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


  • 0
    R

    about python


  • 0
    R
    This post is deleted!

  • 0
    R

    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?


  • 1

    @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.


  • 0
    R

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


Log in to reply
 

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