cpppro

Swapping nodes in a single linked list

In C Tidbits, Data Structures in C/C++ on January 12, 2008 at 4:29 pm

Here is algorithm for swapping two nodes in linked list..

//A complete swap algorithm which cares of
//several scenarios while swapping two nodes in
//a linked list which doesn't have any special nodes
//scenarios considered while swapping
//1)two nodes which are far away
//2)two nodes which are far away, one is node is at
//  beginning of the list
//3)two node which are neighbors
//4)two nodes which are neibhors,
//  one node is at beginning of the list
Node *SwapNodes(Node *list, Node *node1, Node *node2)
{
  Node *node1prev, *node2prev, *tmp;

  node1prev = FindPrev(list, node1);
  node2prev = FindPrev(list, node2);

  tmp = node2->next;

  //check whether node to swapped is in
  //beggining (i.e. header node)
  if (node1 != list)
  {
    node1prev->next = node2;
  }
  else
  {
    //as we do not have special header node,
    //if the first node and some
    //other node, need to be swapped,
    //then update the list (makes new min node as
    //logical header)
    list = node2;
  }

  //are nodes to be swapped neibgoring nodes?
  if (node1->next == node2)
  {
    //nodes to be swapped are neibhoring nodes,
    //then swap them simply
    node2->next = node1;
    node1->next = tmp;
  }
  else
  {
    //nodes to be swapped are not neibhor nodes,
    //they are apart
    //so, consider all scenarios
    node2->next = node1->next;

    node1->next = tmp;
    node2prev->next = node1;
  }

  return list;
}

Please refer reference code for collection of posts in data structures

[note:I’d used old complier(msvc 6.0), if you are using a new compiler you may get some compiler warnings, please solve it yourself or post it here with the problems)

if you find any bugs in the above program post them as comments..

Advertisements
  1. How about swapping nodes in double linked lists and in circular lists? are you going to write them to soon? please let me know

  2. Other Method:

    void swap(LIST &l, NODE *p, NODE *q)
    {
    // Use tmp to save Head

    NODE *tmp = new NODE;
    tmp->pNext = l.pHead;
    l.pHead= tmp;

    NODE *pPrev = FindPrev(l,p);
    NODE *qPrev = FindPrev(l,q);
    NODE *pAfter=p->pNext;

    pPrev->pNext=q;
    p->pNext=q->pNext;
    q->pNext=pAfter;
    qPrev->pNext=p;

    //After swap, move Head
    // Delete tmp
    l.pHead=l.pHead->pNext;
    tmp->pNext=NULL;
    delete tmp;

    }

    😀 Have fun it! pass 2hr to completed this functions

  3. Hi,
    Your code will not work until you pass
    Node **list

  4. Dear Duc Huy:
    Your code is a massive FAIL
    I can’t believe u spent 2 hours on a worthless piece of crap u little pathetic fagmunch

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: