Single Linked List

Reverse a linked list

Given a linked list, convert it in reverse order.

Solution:

[code]

void Reverse(Node * &Gptr)
{
     Node *prev = NULL;
     Node *cur = GPtr;
     Node *next;
     while(cur != NULL)
     {
         next = cur->nextptr;
         cur -> nextptr = prev;
         prev = cur;
         cur = next;
     }
     GPtr = prev;
}

[greeksforgreeks]Merge two sorted linked lists

Solution1: 
Using recursion

[code]

Node * MergeLists(Node *list1, Node *list2)
{
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    if (list1->value < list2 ->value) {
        list1->nextptr = MergeLists(list1->nextptr, list2);
        return list1;
    }
    else {
        list2->nextptr = MergeLists(list2->nextptr, list1);
        return list2;
    }
}

Solution2: similiar to Solution 1. However avoid using recursion, but this needs to understand some pointer tricks, use a pointer to pointers: tail and point to the current qualified node in either one of two lists.

[code]

Node *MergeLists(Node *list1, Node *list2)
{
      Node *mlist, **tail;
      for(mlist= NULL, tail = &mlist; list1 && list2; tail = &(*tail)->nextptr) 
      {
           if (list1->content < list2->content) {
               *tail = list1; list1 = list1->nextptr;
           } 
           else {
                *tail = list2; list2 = list2->nextptr;
           } 
      } 
      *tail = list1? list1: list2;
      return mlist; 
}

Solution3:

[code]

Node *MergeLists(Node *list1, Node *list2) 
{
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    Node *head;
    if (list1->content < list2->content) {
      head = list1;
    } else {
      head = list2;
      list2 = list1;
      list1 = head;
    }

    while(list1->nextptr != NULL) {
      if (list1->nextptr->content > list2->content) {
         Node *tmp = list1->nextptr;
         list1-> nextptr = list2;
         list2 = tmp;
       }
       list1 = list1->nextptr;
    }

    if (list1->nextptr == NULL) list1->nextptr = list2;
    return head;
}

Solution4: similar to Solution3, but easier to understand.

[code]

Node *MergeLists(Node  * list1,  Node *list2)
{
   if(list1 == NULL)
      return list2;
   else if (list2 == NULL)
      return list1;

   Node *head;
   if(list1->content < list2->content)
   {
      head = list1;
      list1 = list1->nextptr;
   } else
   {
      head = list2;
      list2 = list2->nextptr;
   }

   Node *current = head;
   while((list1 != NULL) ||( list2 != NULL))
   {
      if(list1 == NULL) {
         current->nextptr = list2;
         return head;
      }
      else if (list2 == NULL) {
         current->nextptr = list1;
         return head;
      }

      if(list1->content < list2->content)
      {
          current->nextptr = list1;
          list1 = list1->nextptr;
      }
      else
      {
          current->nextptr = list2;
          list2 = list2->nextptr;
      }
          current = current->nextptr;
   }

   current->nextptr = NULL; // needed to complete the tail of the merged list
   return head;

}

Find a mth to last element of a linked list

Given a singly linked list, find the mth-to-last element of the list. If m = 0, return the last element.

Solution 1: scan once to find the number of nodes n, and then scan again to find (n-m)-th element.

Solution 2: use two pointers, one is m element ahead and advance both at the same time.

[code]

Node *findMToLast(Node *head, int m) 
{
    Node *current, *mbehind;
    if (head == NULL) return NULL;
    
    current = head;
    for (int i= 0; i< m; i++) {
       if (current->next != NULL) current = current -> next;
       else return NULL;

    mbehind = head;
    while(current -> next != NULL) { 
        current = current -> next;
        mbehind = mbehind -> next;   
    }

    return mbehind;
}

Reverse a linked list in group.

Given a linked list, please reverse it in group, that is to say
for example:

1->2->3->4->5->6->7->8->9->10, 

after the function:

Node *reverseGroup(Node *head, int start, int len) 

reverseGroup(Node *head, 5, 3) is called,

it becomes 1->2->3->4->5->8->7->6->10. (assume that the 5th node and (5+3)th node are both in the list)

Solution:

[code]

Node *reverseGroup(Node *head, int start, int len)
{
    Node *r = head;
    while(r->next&& (--start)) r = r->next;
    if (!r->next) return NULL;
    Node *pre = head;
    Node *cur = r->next;
    Node *next = NULL;
    while(cur&&(len--)){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    r->next->next = next;
    r->next = pre;
    return head;
}

Insert sort a linked list.

Solution:

[code]

Node *sortLinkList(Node *head)
{
     if(!head|| !head->next) return head;
     Node preNode(-1);
     preNode.next = head;
     Node *run = head;
     while(run&&run->next) {
         if(run->value < run->next->value) {
             run = run -> next;
             continue;
         }
         Node *pre = &preNode;
         while(pre->next->value < run->next->value) {
              pre = pre->next;
         }
//       swap(pre->next->value, run->next->value);  // swap also ok but it is not "insert"
         Node *tmp = pre->next;
         pre->next = run->next;
         run->next = run->next->next;
         pre->next->next = tmp;
     }
     return preNode.next;

}

Reorder nodes:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4,5,6}, reorder it to {1,6,2,5,3,4}.

Solution:

1) using fast, slow pointer to split the lists into two linked lists;

2) reverse the second one;

3) alternately merge these two lists; 

[code]

Node * ReorderList(Node *p)
{
    Node *fast = p;
    Node *slow = p;
    Node *plist = p;
    while(fast->next&& fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }

    Node *rlist = reverseLinkedList(slow->next);   //refer to the above solutions.
    slow->next = NULL;

    // merge p and rlist

    Node preNode(-1);
    Node *vp = &preNode;

    while(plist&&rlist){
        vp->next = plist; plist=plist->next;
        vp = vp->next;
        vp->next = rlist; rlist=rlist->next;
        vp = vp ->next;
    }
    return preNode.next;
}