Swap every two nodes in a linked list

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

5 Thoughts on “Swap every two nodes in a linked list

  1. 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.

  2. Puneet Singh on July 19, 2014 at 6:23 pm said:

    thre is a bug in this plz check

  3. This is a faulty code, not working in any language.

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

    }

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation