Related Blog Items

• Sorting A Linked List with Bubble Sort
• Sorting a Linked List with Selection Sort
• Reversing a double linked list
• Reversing a circular single linked list using pointers
• Reversing a single linked list using stack

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

Download full source code swapping two nodes in linked list

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

Popularity: 33%

You need to log on to convert this article into PDF

Related Blog Items

• Sorting A Linked List with Bubble Sort
• Sorting a Linked List with Selection Sort
• Reversing a double linked list
• Reversing a circular single linked list using pointers
• Reversing a single linked list using stack

This entry was written by ponnada and posted on January 12, 2008 at 4:29 pm and filed under C Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.