Reverse the pairs of elements in a single linked list

Given a single linked list write a function to swap each pair of nodes by manipulating with pointers (not values ). If last element does not have a pair, then leave it as is.

For example:
Original list: head->1->2->3->4->5->NIL should be transformed to head->2->1->4->3->5-> NIL

Optimization note: this algorithm can be implemented with one cycle and without IF statements.

Good luck!

Notify me when a new comment is posted

Comments:

I got it!
By sfomra on Thursday, March 08, 2007 (UMST)

this is kinda simple

heres the solution code

int get_length_of_list(linked_list* node)// returns length od linked list
{
int count = 0;
if(node == NULL)
{
 printf("the list is empty");
 return 0;
}
while(node != NULL)
{
 node = node->next;
 count++;
}
return count;
}

int reverse_pair_elems_of_list(linked_list** head))// reverses pairs of items of a list
{
linked_list* temp = NULL;
linked_list* current_pair = *head;
linked_list** previouspair = head;
for(int i=0; i<get_length_of_list(*head)/2; i++)
{
 temp = current_pair;
 current_pair = current_pair->next;
 temp->next = current_pair->next;
 current_pair->next = temp;
 *previouspair = current_pair;
 current_pair = temp->next;
 previouspair = &temp->next;

}
return 0;
}

Reply to this Comment

resumitting code
By sfomra on Thursday, March 08, 2007 (UMST)

jus resubmetting the code.. with formatting

int get_length_of_list(linked_list* node)// returns length od linked list
{
int count = 0;
if(node == NULL)
{
printf("the list is empty");
return 0;
}
while(node != NULL)
{
node = node->next;
count++;
}
return count;
}

int reverse_pair_elems_of_list(linked_list** head))// reverses pairs of items of a list
{
linked_list* temp = NULL;
linked_list* current_pair = *head;
linked_list** previouspair = head;
for(int i=0; i<get_length_of_list(*head)/2; i++)
{
temp = current_pair;
current_pair = current_pair->next;
temp->next = current_pair->next;
current_pair->next = temp;
*previouspair = current_pair;
current_pair = temp->next;
previouspair = &temp->next;

}
return 0;
}

Reply to this Comment

heres the code without using the get length function
By sfomra on Friday, March 09, 2007 (UMST)

int reverse_pair_elems_of_list(linked_list** head)
{
linked_list* temp = NULL;
linked_list* current_pair = *head;
linked_list** previouspair = head;
while((current_pair != NULL) && (current_pair->next != NULL))
{
temp = current_pair;
current_pair = current_pair->next;
temp->next = current_pair->next;
current_pair->next = temp;
*previouspair = current_pair;
current_pair = temp->next;
previouspair = &temp->next;
}
return 0;
}

Reply to this Comment

what about this?
By michbex on Saturday, March 10, 2007 (UMST)

Of course, there is one if inside, but should be faster: void swapElems() { NODE* pair1 = pHead; NODE* pair2 = pHead->pNext; NODE* last = NULL; pHead = pair2; while (pair1 != NULL && pair1->pNext != NULL) { pair2 = pair1->pNext; if (last != NULL) last->pNext = pair2; pair1->pNext = pair2->pNext; pair2->pNext = pair1; last = pair1; pair1 = pair1->pNext; } } any comments?
Reply to this Comment

think its da same
By sfomra on Sunday, March 11, 2007 (UMST)

think both run with the time complexity of O(n)

here is a more secure version of the code with the check before reassigning the head so that if there is no second elem in the linked list the head still points to the first element

void swapElems()
{
NODE* pair1 = pHead;
NODE* pair2 = pHead->pNext;
NODE* last = NULL;
if(pair2 != NULL)
  pHead = pair2;
while (pair1 != NULL && pair1->pNext != NULL)
{
  pair2 = pair1->pNext;
  if (last != NULL)
   last->pNext = pair2;
  pair1->pNext = pair2->pNext;
  pair2->pNext = pair1;
  last = pair1;
  pair1 = pair1->pNext;
}
}

Reply to this Comment

with 3 pointers
By dss on Wednesday, March 14, 2007 (UMST)

<pre> if ( ! (*phead) ) return; elem_t *prev, *curr, *next; curr = *phead; prev = NULL; next = (*phead)->next; while ( curr && next ) { if ( prev ) prev->next = next; else *phead = next; curr->next = next->next; next->next = curr; prev = curr; curr = curr->next; next = curr!=NULL?curr->next:NULL; }
Reply to this Comment

Simplest one :)
By kdusilvestre on Friday, March 16, 2007 (UMST)

void swap() { node * aux, aux2 = NULL; node * last = head; while(last->next != NULL) { aux = last->next; aux2 = last->next->next; aux->next = aux2->next; aux2->next = aux; last->next = aux2; last = aux; } }
Reply to this Comment

another approach
By nguyen_a on Thursday, May 03, 2007 (UMST)

void reversepair(PNODE *head)
{
   PNODE ptr = (*head)->next;
   (*head)->next = ptr->next;
ptr->next = *head;
*head = ptr;
ptr = ptr->next;
while (ptr->next->next != NULL)
{
      PNODE ptr1 = ptr->next;
      PNODE ptr2 = ptr->next->next;
      ptr1->next = ptr2->next;
      ptr2->next = ptr1;
      ptr->next = ptr2;
      ptr = ptr1;
}
}

Reply to this Comment

java
By nadteks on Thursday, May 10, 2007 (UMST)

I did it in Java because I'm a Java person. class SSL{ private SSLelement doReverse(SSLelement myObj){ SSLelement nextElement; while(myObj==null||(nextElement = myObj.tail)==null) return myObj; myObj.tail = doReverse(nextElement.tail)); nextElement.tail = myObj; return nextElement; } public static void main(String[] args){ mySSL.head=mySSL.doReverse(mySSL.head); } }
Reply to this Comment

Average Rating:

easy swaping
By hoan on Monday, September 24, 2007 (UMST)

Just swap the values easy and clear and works fine, change char* for any data type

void List::Swap()
{
Node* node = first;
while(node)
{
  if(!node->next)
   break;
  char *tmp = node->elem;
  node->elem = node->next->elem;
  node->next->elem = tmp;
  node = node->next->next;
}
}

Reply to this Comment

Reverse Adjacent
By kandukondein on Sunday, February 17, 2008 (UMST)

void ReverseAdjacent()
{
node *temp = start;
node *backup=0;
node *nexttotemp;
while(temp->next!=0 && temp->next->next!=0)
{
  backup=temp;
  temp = temp->next;
  nexttotemp = temp->next;
  temp->next = nexttotemp->next;
  backup->next = nexttotemp;
  nexttotemp->next = temp;
}
}
Reply to this Comment

Code
By thephoenics on Wednesday, February 27, 2008 (UMST)

<pre> 1 swap(int *node) { 2 sllist ptr, ptemp; 3 for(ptr = node, ptemp = 0; ptr && ptr->pnext ; ptemp = ptr, ptr = ptr->pnext->pnext) { 4 sllist = ptr->pnext; 5 ptr->pnext = ptr->pnext->pnext; 6 sllist->pnext = ptr; 7 if (ptemp) ptemp->pnext = sllist; 8 else head = ptemp; 9 } 10 }</pre>
Reply to this Comment

Solution in C#
By kp.zeus on Saturday, July 05, 2008 (UMST)

static void SwapAlternateElements(LinkElement list) { LinkElement temp = list; int index = 0; object currentValue = null; while (temp != null) { if (temp.Next != null) { if (index % 2 == 0) { currentValue = temp.Data; temp.Data = temp.Next.Data; temp.Next.Data = currentValue; } } temp = temp.Next; index++; } } public class LinkElement { private object data; public object Data { get { return data; } set { data = value; } } private LinkElement next; public LinkElement Next { get { return next; } set { next = value; } } public LinkElement(object data, LinkElement next) { this.data = data; this.next = next; } }
Reply to this Comment

using pointer to pointer make the code cleaner
By sleepingmole on Tuesday, August 26, 2008 (UMST)

as elegant as possible~ void pair_reverse(Node ** head) { while(*head&&(*head)->next) { Node * temp=(*head)->next; (*head)->next=temp->next; temp->next=(*head); (*head)=temp; head=&(*head)->next->next; } }
Reply to this Comment

Add Your Comment