Last active
August 29, 2015 14:21
-
-
Save mrkline/201b4b8a550c734a9335 to your computer and use it in GitHub Desktop.
Swapping linked list pairs with two pointers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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