Pairwise swap linked list nodes
This problem was asked by Google.
Given the head of a singly linked list, swap every two nodes and return its head.
For example, given 1 -> 2 -> 3 -> 4
, return 2 -> 1 -> 4 -> 3
.
My Solution(C++):
#include <iostream>
struct Node{
int data;
Node *next;
};
Node *createNode(int data){
Node *temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
void printLinkedList(Node *head){
while (head->next!=NULL){
std::cout<<head->data<<" --> ";
head = head->next;
}
std::cout<<head->data<<std::endl;
}
Node *swapEveryTwo(Node *head){
Node *curr = head;
while (curr->next!=NULL && curr->next->next!=NULL) {
int cache = curr->data;
curr->data = curr->next->data;
curr->next->data = cache;
curr = curr->next->next;
}
return head;
}
void test(){
std::cout<<"\nTest Case 1\n";
Node *head = createNode(1);
Node *curr = head;
for (int i=2; i<=4; i++){
curr->next = createNode(i);
curr = curr->next;
}
std::cout<<"Original Linked List"<<std::endl;
printLinkedList(head);
Node *swapped = swapEveryTwo(head);
std::cout<<"Modified Linked List"<<std::endl;
printLinkedList(swapped);
std::cout<<"\nTest Case 2\n";
head = createNode(1);
curr = head;
for (int i=2; i<=3; i++){
curr->next = createNode(i);
curr = curr->next;
}
std::cout<<"Original Linked List"<<std::endl;
printLinkedList(head);
swapped = swapEveryTwo(head);
std::cout<<"Modified Linked List"<<std::endl;
printLinkedList(swapped);
std::cout<<"\nTest Case 3\n";
head = createNode(1);
curr = head;
for (int i=2; i<=10; i++){
curr->next = createNode(i);
curr = curr->next;
}
std::cout<<"Original Linked List"<<std::endl;
printLinkedList(head);
swapped = swapEveryTwo(head);
std::cout<<"Modified Linked List"<<std::endl;
printLinkedList(swapped);
}
int main(){
test();
return 0;
}