public class List2 {
    ListNode prehead;
    List2() {
        prehead = new ListNode(0,null);
    }

    static void searchInsert(List2 l, int key, int v) {
        // neuen Knoten mit Wert v vor dem Knoten mit wert key in l einfuegen
        // bzw. am Ende
        ListNode previous = l.prehead;
        ListNode n = previous.next;
        while (n != null && n.val != key) {
            previous = n;
            n = n.next;
        }
        ListNode newnode = new ListNode(v, n);
        previous.next = newnode;
    }




    public static void main(String [] args) {
        List2 l1=new List2();
        l1.prehead.next = new ListNode(1, new ListNode(3,null));
        ListNode.print(l1.prehead.next);
        searchInsert(l1, 3, 5);
        ListNode.print(l1.prehead.next);
        searchInsert(l1, 1, 7);
        ListNode.print(l1.prehead.next);
        searchInsert(l1, 5, 8);
        ListNode.print(l1.prehead.next);
        // Einfuegen am Ende testen
        searchInsert(l1, 99, 9);
        ListNode.print(l1.prehead.next);
    }
}