## Adobe Interview Question Software Engineer / Developers

• 0

Write an algorithm to split a circular linked list two linked list with equal no of nodes

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

traverse the circular list with 2 points "first and second"
increment first by 2 times and second once till you read the head pointer again.
after the first travelsal, first will be pointing to head of list and second will be at the mid point.
we will be left with setting the next pointers to null and returning 2 pointer (first and second)

``````//first points to start if the list
void circular_to_list(struct node *first, struct node *second)
{
struct node *head, struct node *temp;
do
{
first = first->next;
if(first == temp)
break;
first = first->temp;
second = second->next;
}while(first != temp);

//first is pointing to head of list
//second is point to mid of the list
temp = first;
first = first->next;
temp->next = NULL;
temp = second;
second = second->next;
second->next = NULL;
}``````

Comment hidden because of low score. Click to expand.
0

temp and head is not initialized in before first loop

Is temp = head = first ?

Comment hidden because of low score. Click to expand.
0

What if list size is odd, then First will skip the head.

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can start with head and assign first node to list1 and next node to list2 and so on... till all the node && node->next are not equal.
But,what if no. of nodes in list has odd value?

Comment hidden because of low score. Click to expand.
0

I think the idea is to not use any additional data structures and do a split in place

Comment hidden because of low score. Click to expand.
0
of 0 vote

Take two pointer of any node, let X. Increment one pointer by one and other by two. when 2nd pointer will again reach to the X then first one will be in the middle of list.Then we will have two list of equal length. First ones starting address will be X and other ones will be 1st pointer.And along with this we need to make lastNode->next=null for both the list.

Comment hidden because of low score. Click to expand.
0

I guess this doesn't work for linked lists with odd-number of elements, does it?.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is same as finding middle element in a link-list by single traversal . Take t1o pointer one runs single increment one 2*single increment. When reached to the middle point split them. Stop condition will not be NULL here but the head pointer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use fast & slow pointer concept ....easy one from Adobe...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use fast & slow pointer concept ....easy one from Adobe...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution given will work for a circular single linked list that has even number of nodes, what if there are odd number of nodes as ptripa pointed out ?

Comment hidden because of low score. Click to expand.
0

A simple condition does the trick.

Solution in coming post.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.career.ds.linkedlist;

public class SplitCircularList {

public static void main(String args[]) {
CreateCircularList ll = new CreateCircularList();
}
}

class CreateCircularList {

public Node createList(int length, int data) {
for (int i = 1; i < length; i++) {
Node temp = new Node((data++));
pointer.setNext(temp);
pointer = temp;
}
}

System.out.print(temp.getData() + "->");
temp = temp.getNext();
}
System.out.println(temp.getData() + "->");
}

harePointer = harePointer.getNext().getNext();
tortoisePointer = tortoisePointer.getNext();
}
temp = temp.getNext();
}
}
}``````

Odd
===

1->2->3->4->5->6->7->
1->2->3->4->
5->6->7->

Even
====

1->2->3->4->5->6->7->8->
1->2->3->4->
5->6->7->8->

Comment hidden because of low score. Click to expand.
0

when will below condition be satisfied ???

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private void splitNode(LLNode head){

int count = 0;

//count total nodes

count++;
temp = temp.next;
}

int i=0;
while(i!=count/2){

temp=temp.next;
i++;

}
//go to middle and ground the node also mark the next node as

temp.next = null;

temp=temp.next;
}
//ground the last node of second list
temp.next=null;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Take 3 pointer from start ..
Increase 1st by 4 times,
Increase 2nd by 2 times,
Increase 3rd by 1 times,

When 1st and 2nd will be meeting for first time, 3rd pointer will on mid

Comment hidden because of low score. Click to expand.
0
of 0 vote

Take 3 pointer from start ..
Increase 1st by 4 times,
Increase 2nd by 2 times,
Increase 3rd by 1 times,

When 1st and 2nd will be meeting for first time, 3rd pointer will on mid

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is another approach....

1. Turn circular list into singly linked list by inserting a null pointer.

2. Now use two pointers, first moves one step at a time while second moves two step at a time. When second reaches the end, first is at middle. Now we can break the list at the middle.

while(second!= NULL && second->next != NULL)
{
first = first->next;
second = second->next->next;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
int move =0;

{
ptr1 = ptr1->next;
i++;
if( i%2 == 0)
{
ptr1 = ptr1->next;
}
}
ptr1->next = NULL;
ptr2->next = NULL;
}
}

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Are you assuming that this is Double linked list?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.