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;
}
}
}