Adobe Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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?
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.
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 ?
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->
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;
}
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;
}
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)
- mtsingh April 25, 2012