Skip to content

Instantly share code, notes, and snippets.

@mrkline
Last active August 29, 2015 14:21
Show Gist options
  • Save mrkline/201b4b8a550c734a9335 to your computer and use it in GitHub Desktop.
Save mrkline/201b4b8a550c734a9335 to your computer and use it in GitHub Desktop.
Swapping linked list pairs with two pointers
#include <cstdio>
struct Node {
int data;
Node* next;
};
Node* makeList(int count)
{
Node* const head = new Node();
Node* prev = head;
head->data = 1;
for (int i = 1; i < count; ++i) {
Node* nn = new Node();
nn->data = i + 1;
prev->next = nn;
prev = nn;
}
return head;
}
void walk(Node* head)
{
while (head != nullptr) {
printf("%d\n", head->data);
head = head->next;
}
}
// The interesting bit
// Double-pointer magic borrowed form Linus (he's smart):
// http://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list
void swapPairs(Node** n)
{
// There must be another two to swap
while(*n != nullptr && (*n)->next != nullptr) {
// Get a pointer to the node that follows this pair
Node* const afterPair = (*n)->next->next;
// Assign the second node's "next" to the first node
(*n)->next->next = *n;
// Assign the pointer to the first node to the second node
*n = (*n)->next;
// Assign the first node's "next" to the node after these two
(*n)->next->next = afterPair;
// Advance two
n = &((*n)->next->next);
}
}
int main()
{
Node* head = makeList(5);
printf("Originally:\n");
walk(head);
swapPairs(&head);
printf("\nAfter:\n");
walk(head);
return 0;
}
/* prints
Originally:
1
2
3
4
5
After:
2
1
4
3
5
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment