I'm familiar with java and have made many data structures there. Not so much in C and to complicate it the professor wants the LL set up LISP style.

I know I need to iteratively sort the tail then insert, but the setup we were given lacks some of the pointers I'm used to. Here is the relevent code so far:

```
typedef struct Node{
int data;
struct Node *nextPtr;
}Node;
typedef Node *List;
List sortList (List L){
if (isEmpty(L)||getRest(L)==NULL) return L;
List rest = getRest(L);
int val = getFirst L;
if (val<=getFirst(rest)) rest = makeList(val, rest);
else rest = insertInto(val, rest);
}
int getFirst (List L) { return L->data;}
List getRest (List L) { return L->nextPtr;}
int isEmpty (List L){
return L==NULL;
}
List emptyList() {
return (List) 0;
}
List makeList (int x, List L){
List result = (List) malloc(sizeof(Node));
result->data = x;
result->nextPtr = L;
return result;
}
```

So the only thing I'm missing is insertInto. The main thing I'm not sure of is how to step through the list like I would with java.

IE

```
public void insert (E data){
Node<E> newNode = new Node<E> (data);
Node<E> previous = null, current = head;
while (current!= null && ((Comparable<E>) data).compareTo (current.data) > 0)
{
previous = current;
current = current.next;
}
if (current == null) tail = newNode;
if (previous==null){
newNode.next = head;
head = newNode;
}
else
{
previous.next = newNode;
newNode.next = current;
}
}
```

Any help would be most appreciated.