by Linked List is a data structure used for storing collection of data where successive elements are connected through pointers and the size of linked list can grow or shrink dynamically.
In short, Linked list can be thought as similar to array in which traversal can happen through pointers instead of indexes. Before going ahead have a look into Linked List Basics and Linked List Implementation.
Let’s have a look on basic class definition for Linked List.
class LinkedList
{
public:
int data;
LinkedList* next;
LinkedList (int data);
~LinkedList ();
};
/* Below function will print all nodes in a Linked List */
void print_linked_list (LinkedList* start)
{
if (!start)
{
cout << "Linked list is null, nothing to print" << endl;
return;
}
LinkedList* temp = start;
while (temp)
{
cout << " " << temp -> data;
temp = temp -> next;
}
cout << endl;
}
Swap K nodes
Swapping K nodes in Linked List means breaking Linked List into small linked list of K nodes and then reversing the order of nodes in these smaller Linked List nodes.
Let’s look into the below figure to make it more clear.
As shown in the above image, Output Linked List nodes are swapped in K nodes clusters.
Algorithm to Swap K nodes
- Start from the Head Node
- Take K nodes at a time and reverse these.
- Repeat above steps with next pair of nodes till we reach the end of Linked List.
Swap K nodes using Recursion
Let’s look into the sample code
LinkedList* swap_k_nodes_using_recursion (LinkedList* start, int k)
{
LinkedList* prev = NULL;
LinkedList* cur = start;
LinkedList* next = NULL;
int counter = 0;
while (cur && counter < k)
{
next = cur -> next;
cur -> next = prev;
prev = cur;
cur = next;
counter++;
}
if (next)
start -> next = swap_k_nodes_using_recursion (next, k);
return prev;
}
Swap K nodes pairwise using Iteration
Let’s look into the sample code.
LinkedList* return_kth_node (LinkedList* node, int k)
{
LinkedList* temp = node;
int counter = 0;
while (temp && counter < k)
{
temp = temp -> next;
counter++;
}
return temp;
}
LinkedList* swap_k_node_linked_list_iteration (LinkedList* node, int k)
{
int counter = 0;
LinkedList* kth_node = return_kth_node (node, k);
if (!kth_node)
return node;
LinkedList* newHead = return_kth_node (node, k-1);
LinkedList* prev = NULL;
LinkedList* cur = node;
LinkedList* next = NULL;
LinkedList* tempHead = NULL;
while (cur && kth_node)
{
counter = 0;
prev = return_kth_node (cur, k);
if (tempHead)
tempHead -> next = kth_node;
tempHead = cur;
while (counter < k)
{
counter++;
next = cur -> next;
cur -> next = prev;
prev = cur;
cur = next;
}
kth_node = return_kth_node (cur, k-1);
}
return newHead;
}
Let’s define a main function to use above methods.
Few of the functions used below are explained in Linked List Insert operation, Linked List Delete Operation and Linked List Traverse and Search article . Refer those before moving ahead.
int main ()
{
LinkedList* start = NULL;
print_linked_list (start);
insert_at_begining (&start, 3);
insert_after_certain_element (start, 5, 6);
insert_after_certain_element (start, 7, 5);
insert_after_certain_element (start, 9, 8);
insert_after_certain_element (start, 11, 10);
insert_after_certain_element (start, 16, 11);
insert_after_certain_element (start, 2, 9);
insert_after_certain_element (start, 15, 2);
insert_after_certain_element (start, 21, 2);
insert_after_certain_element (start, 23, 3);
insert_after_certain_element (start, 35, 5);
insert_after_certain_element (start, 1, 11);
print_linked_list (start);
cout << "Swapping Pairwise Linked List Using Iteration" << endl;
start = swap_k_node_linked_list_iteration (start, 3);
print_linked_list (start);
cout << "Swapping Pairwise Linked List Using Recursion" << endl;
start = swap_k_nodes_using_recursion (start, 3);
print_linked_list (start);
cout << "Deleting Head Node " << endl;
delete_start_node (&start);
print_linked_list (start);
cout << "Deleting Node 11" << endl;
delete_searched_node (&start, 11);
print_linked_list (start);
cout << "Deleting all Nodes" << endl;
delete_all_node (&start);
print_linked_list (start);
}
Let’s analyze the output of this main function.
Linked list is null, nothing to print
Inserting node 5
Searched data not found, hence putting new node at the end
Inserting node 7
Inserting node 9
Searched data not found, hence putting new node at the end
Inserting node 11
Searched data not found, hence putting new node at the end
Inserting node 16
Inserting node 2
Inserting node 15
Inserting node 21
Inserting node 23
Inserting node 35
Inserting node 1
3 23 5 35 7 9 2 21 15 11 1 16
Swapping Pairwise Linked List Using Iteration
5 23 3 9 7 35 15 21 2 16 1 11
Swapping Pairwise Linked List Using Recursion
3 23 5 35 7 9 2 21 15 11 1 16
Deleting Head Node
23 5 35 7 9 2 21 15 11 1 16
Deleting Node 11
Node found, going to delete
23 5 35 7 9 2 21 15 1 16
Deleting all Nodes
Linked list is null, nothing to print
