Ytdyklly

GeeksForGeeks challenge:

Given a singly linked list, write a function to swap nodes pairwise.

For example :

if the linked list is 1->2->3->4->5->6->7 then the function should
change it to 2->1->4->3->6->5->7, and if the linked list is
1->2->3->4->5->6 then the function should change it to
2->1->4->3->6->5

#include <iostream>



// structure of a Node in the linked list

struct Node {

    int data;

    Node *next;

};



// append data to end of linked list

Node *append(Node *head, int data) {

    auto newNode = new Node{data, nullptr};

    if (head == nullptr)

        return newNode;



    auto temp{head};

    while (temp->next)

        temp = temp->next;

    temp->next = newNode;



    return head;

}



//  display the list



void display(Node *head) {

    std::cout << "The list : t";

    while (head != nullptr) {

        std::cout << head->data << " ";

        head = head->next;

    }

    std::cout << std::endl ;

}



//  pairwise swap of the elements in the given linked lists

void pairwiseSwap(Node **head_ref) {



    if(((*head_ref) == nullptr) || ((*head_ref)->next == nullptr))

        return ;



    Node *temp1 = nullptr, *temp2 = nullptr ;

    Node *prev = nullptr, *curr =(*head_ref) ;



    while(curr != nullptr) {



        //  temp1 : first element of the pair

        //  temp2 : second element of the pair

        temp1 = curr;

        temp2 = curr->next;



        //  if the the 2nd element in the pair is nullptr, then exit the loop

        if(temp2 == nullptr){

            break ;

        }

//      curr = curr->next->next ;



        //  if the current element is head, then previous one must be nullptr

        //  In either case swapping the nodes

        if(prev == nullptr){

            prev = temp1;

            temp1->next = temp2->next;

            temp2->next = temp1;

            (*head_ref) = temp2 ;

        }

        else {      

            temp1->next = temp2->next;

            temp2->next = temp1;

            prev->next = temp2;

            prev = temp1;

        }



        //  moving to the next pair of nodes

        curr = temp1->next ;

    }

}



//  Driver function

int main() {

    Node *a = nullptr ;



    // for odd number of nodes

    a = append(a, 15); 

    a = append(a, 10); 

    a = append(a, 5);  

    a = append(a, 20); 

    a = append(a, 3); 

//  a = append(a, 2);



    pairwiseSwap(&a);



    display(a);



   // for even number of nodes

    a = append(a, 15); 

    a = append(a, 10); 

    a = append(a, 5);  

    a = append(a, 20); 

    a = append(a, 3); 

    a = append(a, 2);



    pairwiseSwap(&a);



    display(a);

}

It's weird that you picked append as your primitive for building test cases, when prepend would be so much simpler and faster — O(1) instead of O(n).

auto newNode = new Node{data, nullptr};

This is a very "modern" way of writing what would be more idiomatically written as

Node *newNode = new Node(data, nullptr);

I would weakly recommend the latter. And I would strongly recommend, if you do nothing else, at least calling out explicitly when you're working with raw (non-owning) pointers:

auto *newNode = new Node{data, nullptr};  // the asterisk means watch out!

auto temp{head};

Again, I'd write simply

Node *temp = head;

or at least

auto *temp = head;

The * signals the reader to watch out for pointer pitfalls (aliasing, memory leaks); the = signals the reader that an initialization is happening here. You might be surprised how easy it is to glance over auto temp{head}; surrounded by other lines of code and not even recognize that it's introducing the name temp!

//  pairwise swap of the elements in the given linked lists

void pairwiseSwap(Node **head_ref) {

Some coding guidelines tell you to pass the inout parameter head_ref by pointer here, instead of by reference. I'm going to assume you're following one of those guidelines.

return ;

is an unidiomatic whitespace style; most programmers would write

return;

You actually put an extra space before a lot of semicolons in this function (but not consistently). Are you French? ;)

You should definitely factor out the "swap two nodes" functionality into a named function. I somewhat suspect that this would do, but you'd have to draw it out on paper...

void swap_two_nodes(Node *&p, Node *&q) {

    assert(p->next == q);

    std::swap(p, q);

}

Alternatively — and since I've confused myself ;) — you could just write a recursive version of the whole thing:

Node *pairwise_swap(Node *head) {

    if (head && head->next) {

        Node *first = head->next;

        Node *second = head;

        Node *tail = pairwise_swap(head->next->next);

        head = first;

        first->next = second;

        second->next = tail;

    }

    return head;

}

Turning this into tail-recursion is left as an (easy) exercise for the reader.

// for even number of nodes

a = append(a, 15); 

Appending an even number of nodes to an odd-length list does not result in an even-length list. Did you try running your test code? Did you look at the output and verify that it was correct? You should have!

Looking at just your pairwiseSwap() function… there are too many special cases.

Every iteration through the loop should verify that there are at least two more elements to process. You shouldn't need a special case to check for if(((*head_ref) == nullptr) || ((*head_ref)->next == nullptr)) return ; to start.

On the other hand, the loop condition should make it clear that at least two nodes are required to proceed. You've obfuscated the check for the second node as if(temp2 == nullptr) { break ; }.

You then have a special case for the first iteration (// if the current element is head, then previous one must be nullptr). That special case would be better handled by introducing a preHead object, whose next points to the original head node.

After eliminating the special cases as described above, and renaming temp1 → a and temp2 → b (because "temp" is nearly always meaningless in a variable name), we get this simple solution:

void pairwiseSwap(Node **head) {

    Node preHead{0, *head};

    for (Node *prev = &preHead, *a, *b; (a = prev->next) && (b = a->next); prev = a) {

        a->next = b->next;

        b->next = a;

        prev->next = b;

    }

    *head = preHead.next;

}