Single Linked List Manipulations

1.Rotate a Linked List
Given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer. For example, if the given linked list is 10->20->30->40->50->60 and k is 4, the list should be modified to 50->60->10->20->30->40. Assume that k is smaller than the count of nodes in linked list.

http://www.geeksforgeeks.org/rotate-a-linked-list/

2.Swap Elements in a Linked List
Given a singly linked list, swap every two elements (e.g. a->b->c->d->e->f->null should become b->a->d->c->f->e->null). Code it such that memory position is swapped and not the node value.
http://www.geeksforgeeks.org/pairwise-swap-elements-of-a-given-linked-list/
http://www.geeksforgeeks.org/pairwise-swap-elements-of-a-given-linked-list-by-changing-links/
http://www.geeksforgeeks.org/swap-nodes-in-a-linked-list-without-swapping-data/

3.Rearrange a given linked list in-place.
Given a singly linked list L0 -> L1 -> … -> Ln-1 -> Ln. Rearrange the nodes in the list so that the new formed list is : L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 …
You are required do this in-place without altering the nodes’ values.
http://www.programcreek.com/2013/12/in-place-reorder-a-singly-linked-list-in-java/
http://www.geeksforgeeks.org/rearrange-a-given-linked-list-in-place/

4.Even and odd positioned nodes are together
Rearrange a linked list such that all even and odd positioned nodes are together
http://www.geeksforgeeks.org/rearrange-a-linked-list-such-that-all-even-and-odd-positioned-nodes-are-together/

5.Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example, given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5
http://www.programcreek.com/2013/02/leetcode-partition-list-java/

public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null) return null;

        ListNode fakeHead1 = new ListNode(0);
        ListNode fakeHead2 = new ListNode(0);
        fakeHead1.next = head;

        ListNode p = head;
        ListNode less = fakeHead1;
        ListNode more = fakeHead2;

        while(p != null){
            if(p.val < x){
                less = less.next;
            }else{

                more.next = p;
                less.next = p.next;
                more = more.next;
            }
            p = p.next;
        }

        // close the list
        more.next = null;
       
        // Connect less list to more
        less.next = fakeHead2.next;

        return fakeHead1.next;
    }
}
6.Rearrange a Linked List
Given a linked list as follows:
a->b->c->1->2->3
Arrange it in a manner it would return
a->1->b->2->c->3
Note:list contains even number of nodes.

Method 1:
maintain two stack...
in stack1 keep on pushing the nodes until some node->data!=numeric value;
now push all numeric node in the stack2.
n1=pop(stack2);
n2=pop(stack1);
n1->next=n2;
keep on doing that until both stack are null

Method 2:
maintain one ptr1 at head.
increment ptr2 till it reaches a node which has numeric value...in the given example its "1";
now remove node at ptr2 and add it to the next of ptr1;
increment ptr1 twice.

7.Reorder the linked list as odd followed by even elements in a single pass
For example:
 13->11->28->45->58->69->34->23->86};
Output should be
13->11->45->69->23->28->58->34->86

http://www.geeksforgeeks.org/segregate-even-and-odd-elements-in-a-linked-list/

8.Rearrange a Linked List in Zig-Zag fashion
Given a linked list, rearrange it such that converted list should be of the form a < b > c < d > e < f .. where a, b, c.. are consecutive data node of linked list. Examples :

Input:  1->2->3->4
Output: 1->3->2->4

Input:  11->15->20->5->10
Output: 11->20->5->15->10

http://www.geeksforgeeks.org/linked-list-in-zig-zag-fashion/

9.Alternating minimum maximum
Given a list of integers, rearrange the list such that it consists of alternating minimum maximum elements using only list operations. The first element of the list should be minimum and second element should be maximum of all elements present in the list. Similarly, third element will be next minimum element and fourth element is next maximum element and so on. Use of extra space is not permitted.
http://www.geeksforgeeks.org/rearrange-given-list-consists-alternating-minimum-maximum-elements/

10. Split a Linked List:
Write FUNCTIONS for following Linked List Splits
1. FrontBackSplit()---Given a list, split it into two sub lists — one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list.
http://articles.leetcode.com/splitting-linked-list/
2. AlternatingSplit()---Takes one list and divides up its nodes to make two smaller lists. The sublists should be made from alternating elements in the original list.
http://www.geeksforgeeks.org/alternating-split-of-a-given-singly-linked-list/
3. Split a Circular List into two halves---
http://www.geeksforgeeks.org/split-a-circular-linked-list-into-two-halves/

FrontBackSplit:Two Pointers Method

void FrontBack_split(struct node* head,struct node *&front_ref,struct node *&back_ref)
{
   struct node *slow_ptr = head;
   struct node *fast_ptr = head;
   //struct node *prev_of_slow_ptr = head;
if (head==NULL || head->link==NULL)
   {
   front_ref = head;
   back_ref = NULL;
   }
else
   {
   while((fast_ptr->link)!=NULL &&
               (fast_ptr->link->link)!=NULL)
       {
          fast_ptr = fast_ptr->link->link;
          slow_ptr = slow_ptr->link;
       }
        front_ref = head;
        back_ref = slow_ptr->link;
        slow_ptr->link = NULL;
   }
}
AlternateSplit:Two Pointer Method

We will first initialise two pointers as first and second node of List.Then go on connecting next of one pointer to next of other pointer and move forward //First Method in Code

Using Dummy pointer Method:
This builds the sub-lists in the same order as the source list. The code uses a temporary dummy header nodes for the ‘a’ and ‘b’ lists as they are being built. Each sublist has a “tail” pointer which points to its current last node — that way new nodes can be appended to the end of each list easily. The dummy nodes give the tail pointers something to point to initially. The dummy nodes are efficient in this case because they are temporary and allocated in the stack. Alternately, local “reference pointers” (which always points to the last pointer in the list instead of to the last node) could be used to avoid Dummy nodes
Code:
#include <stdio.h>
#include<malloc.h>
#include<conio.h>
#include<assert.h>

struct node{
int info;
struct node *link;};

typedef struct node* list;

void Create_List_Single(struct node *& head,int data)//USING A TEMP VARIABLE
{
struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=NULL;

if (head==NULL)
{head=tmp;}
 else
{q=head;
while(q->link!=NULL)
q=q->link;
q->link=tmp;}
}
list alternateNode_best(list head)
{
        list newlist = head->link; // newlist and head are two heads of required Lists
        list temp, p; //For Traversing the List

        for(p = head; p ; p = p->link)
        {
                temp = p->link;
                if(!temp)
                  p->link=temp;
                else
               { p->link = temp->link;
           
                if(temp->link)
                        temp->link = temp->link->link;}
        }
        return newlist;
}

void AlternatingSplit_recursive(struct node* &head, struct node* &A,struct node* &B){
  if(! head ){
    A=NULL;
    B=NULL;
    return;
  }
  if(! head->link ){
    A=head;
    B=NULL;
    return;
  }
  node* current=head;
  A=current;
  B=current->link;
  current=current->link->link;
  AlternatingSplit_recursive(current,A->link,B->link);
}

void MoveNode(struct node** destRef, struct node** sourceRef) {
struct node* newNode = *sourceRef; // the front source node
assert(newNode != NULL);

*sourceRef = newNode->link; // Advance the source pointer
newNode->link = *destRef; // Link the old dest off the new node
*destRef = newNode; // Move dest to point to the new node
}

void AlternatingSplit_WithDummyNode(struct node* source, struct node** aRef,struct node** bRef)
{
  struct node aDummy;
  struct node* aTail = &aDummy; /* points to the last node in 'a' */
  struct node bDummy;
  struct node* bTail = &bDummy; /* points to the last node in 'b' */
  struct node* current = source;
  aDummy.link = NULL;
  bDummy.link = NULL;
  while (current != NULL)
  {
    MoveNode(&(aTail->link), &current); /* add at 'a' tail */
    aTail = aTail->link; /* advance the 'a' tail */
    if (current != NULL)
    {
      MoveNode(&(bTail->link), &current);
      bTail = bTail->link;
    }
  }
  *aRef = aDummy.link;
  *bRef = bDummy.link;
}


void AlternatingSplit_WithMoveNode(struct node* source,struct node** aRef, struct node** bRef)
{

struct node* a = NULL; // Split the nodes to these 'a' and 'b' lists
struct node* b = NULL;
struct node* current = source;

while (current != NULL)
{
    MoveNode(&a, &current);
                    // Move a node to 'a'
      if (current != NULL)
      {
          MoveNode(&b, &current); // Move a node to 'b'
      }
}
*aRef = a;
*bRef = b;
}

void AlternatingSplit_WithoutMoveNode(struct node* source, struct node** aRef,struct node** bRef)
{
    struct node** current_list = aRef;
    struct node* current_node = source;
    struct node* next_node = NULL;

    while (current_node != NULL)
    {
        next_node = current_node->link;
        current_node->link = (*current_list);
        (*current_list) = current_node;
        current_node = next_node;

        current_list = (current_list == aRef) ? bRef : aRef;
    }
}

void AlternatinggSplit_WithoutMoveNodeBetter(struct node* source, struct node** aRef,struct node** bRef)
{
    unsigned exor;
    struct node** current_list = aRef;
    struct node* current_node = source;
    struct node* next_node = NULL;

    /* Smarty compiler, don't warn me,
       I know what I am doing */
    exor = (unsigned)aRef ^ (unsigned)bRef;

    while (current_node != NULL)
    {
        next_node = current_node->link;
        current_node->link = (*current_list);
        (*current_list) = current_node;
        current_node = next_node;

        current_list = (struct node**)((unsigned)current_list ^ exor);
    }
}

void display(struct node *head)
{struct node *q;
if(head==NULL)
{printf("List is empty");
return;
}
q=head;
printf("\nList is\n");
while(q!=NULL)
{printf("%d\n",q->info);
q=q->link;}
}

int main(){
 
       struct node *head=NULL;
       struct node *aRef=NULL;
       struct node *bRef=NULL;

       Create_List_Single(head,34);
       Create_List_Single(head,56);
       Create_List_Single(head,23);
       Create_List_Single(head,9);
       Create_List_Single(head,78);
       Create_List_Single(head,22);
        Create_List_Single(head,98);

       display(head);
   
       AlternatingSplit_WithDummyNode(head,&aRef,&bRef);
    //   AlternatinggSplit(head, &aRef,&bRef);
   //    AlternatingSplit_withoutMoveNode(head, &aRef,&bRef);
    //   AlternatingSplit(head,&aRef, &bRef);
    //   aRef=alternateNode(head);
       //display(head);
       display(aRef);
       display(bRef);

       getch();
       return 0;
        }