Thursday Code Puzzler: Splitting Linked Lists
Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.
Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer. It's all about the participation!
Do you have code puzzlers that you'd like to share with the DZone community? If so, please submit here.
Splitting A Linked List
Write a method that takes a linked list and splits it up into two sub-lists, one for the front half and one for the back. If the number of elements are odd, the extra element goes to the front list.
An example of this would be a complete list of [2,3,4,5,7,11,13] that would give you [2,3,4,5] and [7,11,13]. Remember to use the Linked List data structure.
Catch up on all our previous puzzlers here.
Comments
Vijay Nathani replied on Thu, 2013/03/14 - 5:53am
Groovy
def split(list) { int h = list.size() / 2 + (list.size() % 2) [ list.subList(0,h), list.subList(h, list.size())] } assert [[2,3,4,5],[7,11,13]] == split([2,3,4,5,7,11,13])sun east replied on Thu, 2013/03/14 - 9:37am
By Scala:
/** * usage: split(1::2::3::Nil) */ def split[T](xs: List[T],front: List[T]=Nil,back: List[T]=Nil):(List[T],List[T]) = xs match { case Nil => (front, back) case x :: Nil => split(Nil, front :+ x, back) case p +:m:+ q => split(m, front :+ p, q +: back) }Or simple write as:
Test:
Ulrich Cech replied on Thu, 2013/03/14 - 1:20pm
Java:
/** * Splits a linked list up into two sub-lists, one for the front half * and one for the back. If the number of elements are odd, * the extra element goes to the front list. * * @param list the LinkedList to be split * @return an array of the two sublists; the front half list is in index 0, * the back half list is in index 1 */ public LinkedList[] split(LinkedList list) { LinkedList[] retValue = new LinkedList[2]; int index = (int) Math.ceil(list.size() / 2.0); retValue[0] = new LinkedList(list.subList(0, index)); retValue[1] = new LinkedList(list.subList(index, list.size())); return retValue; }Test-case:
@Test public void test() { LinkedList[] list = split(new LinkedList(Arrays.asList(new Integer[]{2,3,4,5,7,11,13}))); LinkedList[] list2 = split(new LinkedList(Arrays.asList(new Integer[]{2,3,4,5,7,11}))); Assert.assertArrayEquals(new Integer[]{2,3,4,5}, list[0].toArray()); Assert.assertArrayEquals(new Integer[]{7,11,13}, list[1].toArray()); Assert.assertArrayEquals(new Integer[]{2,3,4}, list2[0].toArray()); Assert.assertArrayEquals(new Integer[]{5,7,11}, list2[1].toArray()); }Joshua Goldie replied on Thu, 2013/03/14 - 2:10pm
LinkedList<Integer> list = new LinkedList<>(); list.addAll(Arrays.asList(new Integer[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16})); LinkedList<Integer> first = new LinkedList<>(); LinkedList<Integer> second = new LinkedList<>(); try { while(true) { first.addLast(list.removeFirst()); second.addFirst(list.removeLast()); } } catch (NoSuchElementException e) { //Done! }Nils Lien replied on Wed, 2013/03/20 - 9:45am
Russell Luo replied on Wed, 2013/03/20 - 10:08am
a = [2,3,4,5,7,11,13] b = a[0:(len(a)+1)/2] assert (b==[2,3,4,5])Nicholas Sterling replied on Wed, 2013/03/20 - 3:32pm
Scala:
val nums = List(2,3,4,5,7,11,13)
val (front,back) = nums splitAt (nums.size+1) / 2
Rainer Koppler replied on Thu, 2013/03/21 - 5:29am
split_tlist receives the list to be split. After return, the input list has been reduced to the first half, and the function result points to the second half:
struct tlist_node { struct tlist_node *next; }; typedef struct tlist_node *tlist; int tlist_walk(tlist n, int i, tlist *n2) { int length; if (n == 0) { return i; } length = tlist_walk(n->next, i + 1, n2); if ((length + 1) / 2 - 1 == i) { *n2 = n->next; n->next = 0; } return length; } tlist split_tlist(tlist n) { tlist n2 = 0; if (n != 0) tlist_walk(n, 0, &n2); return n2; }Daniel Sobral replied on Thu, 2013/03/21 - 6:03pm
I was going to skip this, but I'm not really happy with the answers. The solution below isn't really doing any less work than most of them, but it's probably going to have better locality of reference for lists up to a certain size.
import scala.collection.mutable.LinkedList def split[T](list: LinkedList[T]): (LinkedList[T], LinkedList[T]) = { var p1, p2, last = list while(p2.nonEmpty) { p2 = p2.next.next last = p1 p1 = p1.next } val tail = p1 last.next = LinkedList.empty[T] (list, tail) }Andy Vo replied on Fri, 2013/03/22 - 3:19pm
def split(LinkedList list) { int n = 0 LinkedList<Integer> a = [], fifo = []; for (Integer o : list) { fifo.add(o) if (n++ % 2 == 0) a.add(fifo.poll()) } [a, fifo] } void testSplit() { assert [[2,3,4,5], [7,11,13]] == split(new LinkedList([2,3,4,5,7,11,13])) }