// 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.
#include <iostream>
#include <string>
using namespace std;
class Node
{
int data;
public:
Node(int newData)
{
data = newData;
}
int GetData() { return data; };
Node* next;
};
Node* NodeSwap(Node* head)
{
Node* first = head;
Node* second = head->next;
Node* newHead = head->next;
Node* prev = nullptr;
while (first && first->next)
{
second = first->next; // second = 2
// change order
first->next = second->next;
second->next = first;
if(prev)
prev->next = second;
// iterate
prev = first; // prev = 1
first = prev->next;
}
return newHead;
}
int main()
{
Node* list = new Node(1);
list->next = new Node(2);
list->next->next = new Node(3);
list->next->next->next = new Node(4);
list->next->next->next->next = new Node(5);
list->next->next->next->next->next = new Node(6);
Node* newList = NodeSwap(list);
while (newList)
{
cout << newList->GetData() << endl;
newList = newList->next;
}
return 0;
}
Comments