Given a singly linked list, swap every two nodes
e.g. 1->2->3->4->5->6 should become 2->1->4->3->6->5
Solution:
This can be done using two pointers. Take a current and temp pointer. At each iteration swap temp and current node. Repeat the steps until null node. You can think of the recursive solution of the problem.
Implementation:
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
};
ListNode *swapPairs(ListNode* head) {
// trivial cases
if (head == NULL || head->next == NULL) return head;
ListNode *newHead = head->next, *temp;
// Pointer-to-pointer, so that we can update current pointer value.
ListNode **cur = &head;
while (*cur && (*cur)->next) {
temp = (*cur)->next;
(*cur)->next = (*cur)->next->next;
temp->next = *cur;
*cur = temp;
cur = &((*cur)->next->next);
}
return newHead;
}
ListNode *createListFromArray(int arr[], int n) {
ListNode *head = new ListNode;
ListNode *ptr = head;
for (int i = 0; i < n; i++) {
ptr->val = arr[i];
ptr->next = (i == n-1 ? NULL : new ListNode);
ptr = ptr->next;
}
return head;
}
void printList(ListNode *ptr) {
while(ptr) {
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << endl;
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
ListNode *head = createListFromArray(arr, 9);
cout << "Original List: ";
printList(head);
head = swapPairs(head);
cout << "New List: ";
printList(head);
return 0;
}
This wouldn’t work. We would be losing odd nodes. For eg: if the nodes are say 0->1->2->3->4->5 then after 1st iteration the new list would be 1->0->2->3->4->5 and the curr pointer would be at 4 and temp pointer at 3. we expect the result after second iteration to be 1->0->3->2->4->5. This is where the problem is. We can not make link from 0th node to 3rd node as we lost pointer at 0th node.
thre is a bug in this plz check
This is a faulty code, not working in any language.
void SwapEveryTwoNodesInLinkedList(void)
{
struct SingleLinkList *t1,*t2,*t3;
t1=head;
t2=t1->link;
head=t1->link;
t1->link=t2->link;
t2->link=t1;
while(t1)
{
printf(“\n\r ##”);
t3=t1;
t1=t1->link;
t2=t1->link;
t1->link=t2->link;
t3->link=t2;
t2->link=t1;
if((t1->link == NULL) || (t1->link->link == NULL))
t1=NULL;
}
}
void SwapEveryTwoNodesInLinkedList(void)
{
struct SingleLinkList *t1,*t2,*t3;
if(head == NULL)
{
printf(“\n\r List Is Empty…”);
}
else if(head->link == NULL)
{
printf(“\n\r Only One node is present…”);
}
else
{
t1=head;
t2=t1->link;
head=t1->link;
t1->link=t2->link;
t2->link=t1;
if((t1->link == NULL) || (t1->link->link == NULL))
t1=NULL;
while(t1)
{
t3=t1;
t1=t1->link;
t2=t1->link;
t1->link=t2->link;
t3->link=t2;
t2->link=t1;
if((t1->link == NULL) || (t1->link->link == NULL))
t1=NULL;
}
}
}