I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Splitting Linked Lists

03.14.2013
| 5277 views |
  • submit to reddit

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:

def split2[T](xs: List[T]) = xs.splitAt((xs.size+1)/2)

Test:

scala> val (f, b) = split(List(2, 3, 4, 5, 7, 11, 13))
f: List[Int] = List(2, 3, 4, 5)
b: List[Int] = List(7, 11, 13)

scala> val (f2, b2) = split2(List(2, 3, 4, 5, 7, 11, 13))
f2: List[Int] = List(2, 3, 4, 5)
b2: List[Int] = List(7, 11, 13)

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

import scala.collection.mutable.LinkedList
val list = LinkedList(2,3,4,5,7,11,13)
def splitIndex(l: LinkedList[Int]): Int = if (l.length % 2 != 0) l.length / 2 + 1 else l.length / 2 
val (list1, list2) = list.splitAt(splitIndex(list))




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]))
}

Márcio Ferreira replied on Fri, 2013/06/28 - 8:35am

public List<List<Integer>> dividirLista(LinkedList<Integer> lista){
		return Lists.partition(lista, (lista.size()/2 + (lista.size()%2)));
	}

 Using Lists.partition from Guava Api

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.