CareerCup

reArrange(ll){
aList= ll;
	while(ll.data != b1 )
		ll = ll.next;
bList = ll;
ll = aList; //initialized ll to original start

while( aList != null && bList != null ){
	aListNextNode = aList.next;
	aList.next = bList ;
	aList = aListNextNode;
	bListNextNode = bList.next;
	bList.next = aListNextNode;
	bList = bListNextNode;
}
return ll;

}

public static Node transformList(Node head, int n){
Node temp1, temp2, midNode=null;
Node start = head;
temp1 = head;
for(int i=0; i<n/2-1; i++){
midNode = temp1.getNext();
temp1 = midNode;
}

Node swapIndex = reverseList(midNode.getNext());
System.out.println("swap is "+swapIndex.data);
midNode.setNext(null);

return mergeList(head, swapIndex);

}

Node startNode = head;

Node midNode = getMidNode(head);

while(startNode!=null&&midNode!=null)
{
Node startTemp = startNode.getNext();
Node midTemp = midNode.getNext();
startNode.setNext(midNode);
mideNode.setNext(startTemp);
startNode = startTemp;
midNode = midTemp;


}

public void transform(SingleLLNode header) {
        int count = 0;
        SingleLLNode current = header;
        while(current != null) {
            count++;
            current = current.next;
        }
        int start = count/2,iteration = 1;
        while(start > 1) {
            int i = 0;
            current = header;
            while(i< start) {
                current = current.next;
                i++;
            }
            i = 0;
            while (i < iteration) {
                int temp = current.data;
                current.data = current.next.data;
                current.next.data = temp;
                i++;
                current = current.next.next;
            }
            iteration++;
            start--;
        }
    }

class Link {
	public String data;
	public Link next;

	Link() {

	}

	public Link(String data) {
		this.data = data;

	}
}

class InsertLinkList {
	private Link first;

	InsertLinkList() {
		first = null;
	}

	public void intializeLink(String data) {
		Link a = new Link(data);
		if (first == null) {
			first = a;
			a.next = null;
		} else {
			a.next = first;
			first = a;
		}

	}

	public void display(InsertLinkList lin) {
		while (first != null) {
			System.out.println(first.data);
			first = first.next;
		}
	}

	public void display1(InsertLinkList lin) {

		Link first1 = first;
		Link first3 = first;

		while (first1.next != null) {
			System.out.println(first3.data);
			first1 = first3.next.next.next;
			System.out.println(first1.data);
			first3 = first3.next;

		}
	}
}

public class LinkedLista1b1a2b2 {

	public static void main(String[] args) {

		InsertLinkList lin = new InsertLinkList();
		lin.intializeLink("b3");
		lin.intializeLink("b2");
		lin.intializeLink("b1");

		lin.intializeLink("a3");
		lin.intializeLink("a2");
		lin.intializeLink("a1");

		lin.display1(lin);
	}

}

Output-
a1
b1
a2
b2
a3
b3

Node rearrange(Node head, Node b1)
{
Node p1 = head;
Node p2,p2_start = head;

if (head == null)
return;
while(p1 != b1)
p2 = p2.next;
Node p1_end = p2;
while(p1!=p2_start && p2!=null)
{
Node t1 = p1.next;
Node t2 = p2;

if (t2!=null)
p1.next = t2;
else //if number of b < number of a
{
p1_end = null;
return head;
}
if (t1!=p2_start)
{
p1.next.next = t1;
p1 = p1.next.next;
p2 = p2.next;
}
else //if number of a < number of b
{
p1.next = p2;
return head;
}
}
return head;
}

/* This code works for any no of nodes */

alternate(struct list *a)
{
	struct list mid,temp,*fptr=a,*sptr=a;	
	int i =0;	
	/* find the middle of the list  */
	while(fptr->next !=  NULL)
	{
		if(i==0)
		{
			fptr=fptr->next;
			i=1;
		}else
		{
			fptr=fptr->next;
			sptr=sptr->next;
			i=0;
		}
	}
	
	fptr = a;
	temp = fptr->next;
	mid = sptr;
	/* Now sptr in the middle of the list and fptr start of the list */
	while(sptr)
	{
		if (sptr == fptr || sptr == temp)
			break;
		fptr->next = sptr;
		sptr = sptr->next;
		fptr = fptr->next;
		if (!sptr || temp == mid)
			break;
		fptr->next = temp;
		temp = temp->next;
		fptr = fptr->next;
		
	}
	if(sptr)
		fptr->next = sptr;
}

Time Complexity : O(n) Space Complexity : O(1)

Same can be achieved by Dynamic programming but takes O(nlog(n))