## Adobe Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 5 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;
head = first;
second = head;
first = head;
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
of 0 votes

temp and head is not initialized in before first loop

Is temp = head = first ?

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

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
of 0 votes

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
of 0 votes

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
of 0 votes

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();
Node head = ll.createList(7, 1);
ll.displayCircularList(head);
Node secondHead =  ll.splitList(head);
ll.displayCircularList(head);
ll.displayCircularList(secondHead);
}
}

class CreateCircularList {

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

public void displayCircularList(Node head) {
Node temp = head;
while (temp.getNext() != head) {
System.out.print(temp.getData() + "->");
temp = temp.getNext();
}
System.out.println(temp.getData() + "->");
}

public Node splitList(Node head) {
Node tortoisePointer = head;
Node harePointer = head.getNext();

while(harePointer != head && harePointer.getNext() != head) {
harePointer = harePointer.getNext().getNext();
tortoisePointer = tortoisePointer.getNext();
}
Node secondHead = tortoisePointer.getNext();
tortoisePointer.setNext(head);
Node temp = secondHead;
while(temp.getNext() != head) {
temp = temp.getNext();
}
temp.setNext(secondHead);
return secondHead;
}
}``````

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
of 0 votes

when will below condition be satisfied ???

while(harePointer != head && harePointer.getNext() != head) {

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

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

LLNode temp = head;
int count = 0;

//count total nodes
while(temp.next!=head){

count++;
temp = temp.next;
}

temp = head;

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

temp=temp.next;
i++;

}
//go to middle and ground the node also mark the next node as
//head of second LL
LLNode newHead = temp.next;

temp.next = null;

temp = newHead;
while(temp.next!=head){
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

Given a circular linked list with head pointer head.

Here is another approach....

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

temp = head->next;
head->next = null;
head = temp;

Now we have a singly linked list with new head 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.

first = head;
second = head;
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

BreakCircular( Linked *head)
{
Linked * ptr1 , *ptr2, head1;
ptr1 = ptr2 = Head;
int move =0;

while( Ptr2->next != Head)
{
ptr1 = ptr1->next;
i++;
if( i%2 == 0)
{
ptr1 = ptr1->next;
}
}
head1 = 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
of 0 votes

Are you assuming that this is Double linked list?

Add a Comment
Name:

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

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More