Mergesort a LinkedList

I have made an attempt to write the mergesort routine on a LinkedList in Java. It will be great if somebody can review my implementation and point out the issues with it.

```
public class LinkedListSort{
static class Node>{
private T value;
private Node next;

public Node(T value,Node next){
this.value = value;
this.next = next;
}

public T getValue(){
return this.value;
}

public void setNext(Node next){
this.next = next;
}

public Node getNext(){
return this.next;
}

@Override
public String toString(){
if(this.next == null){
return this.value.toString();
}else{
return this.value.toString() +"->"+next.toString();
}
}
}
private > Node getLastHalf(Node list){
if(list.getNext() == null) return list;
//Get the last half of the list
Node current = list;
Node mid = list;
int midCounter = 0;
while(current != null){
if(midCounter%2 == 0){
mid = mid.getNext();
}
current = current.getNext();
midCounter++;
}
return mid;
}

private > Node getFirstHalf(Node list){
if(list.getNext() == null) return list;
Node current = list;
Node mid = list;
Node accum = null;
Node accumPtr = accum;
int midCounter = 0;
while(current != null){
if(midCounter%2 == 0){
Node fNode = new Node(mid.getValue(),null);
if(accum == null){
accum = fNode;
accumPtr = accum;
}else{
accum.setNext(fNode);
accum = accum.getNext();
}
mid = mid.getNext();
}
current = current.getNext();
midCounter++;
}
return accumPtr;
}

An initial few comments:

-
You can split your list in one pass, rather than separately getting
the two halves. Here's an example of a split method (I
lazily used javafx.util.Pair, but you can create your own
Pair-like class if you wish).

static > Pair,Node> split(Node list) {

  if (list.getNext() == null)
    return new Pair<>(list, null);

  Node tail = list.getNext();
  Node current = tail;

  // Effectively clone
  Node head = new Node<>(list.getValue(), null);
  Node currentHead = head;

  int midCounter = 0;
  while (current != null) {
    midCounter++;

    if (midCounter % 2 == 0) {
      currentHead.setNext(new Node<>(tail.getValue(), null));  
      currentHead = currentHead.getNext();
      tail = tail.getNext();
    }
    current = current.getNext();
  }

  return new Pair<>(head, tail);
}

-
As a result you'll need to mildly adjust your sort method:

public static > Node sort(Node list) {
  assert (list != null);
  if (list.getNext() == null) {
    return list;
  } else {
    Pair, Node> split = split(list);
    // Sort the first half
    Node left = sort(split.getKey());
    // Sort the other half
    Node right = sort(split.getValue());
    // Merge the sorted left half and right half
    return merge(left, right);
  }
}

-
You've used instance methods where static methods would suffice. I would add a private constructor to your class (since no-one needs to construct it) and change all your methods to static methods.

-
Minor point: you can defer the creation of leftVal and rightVal until inside the if statements in your merge method:

if (left.getValue().compareTo(right.getValue())  leftVal = new Node(left.getValue(), null);
  if (head == null) {
    head = leftVal;
    merged = head;
  } else {
    head.setNext(leftVal);
    head = head.getNext();
  }
  left = left.getNext();
} else {
  Node rightVal = new Node(right.getValue(), null);
  if (head == null) {
    head = rightVal;
    merged = head;
  } else {
    head.setNext(rightVal);
    head = head.getNext();
  }
  right = right.getNext();
}

StackExchange Code Review Q#85279, answer score: 2