public class List1 {
    ListNode head;




    static void searchInsert(List1 l, int key, int v) {
        // neuen Knoten mit Wert v vor dem Knoten mit wert key in l einfuegen
        // bzw. am Ende
        ListNode previous = null;
        ListNode n = l.head;
        while (n != null && n.val != key) {
            previous = n;
            n = n.next;
        }
        ListNode newnode = new ListNode(v, n);
        if (previous == null) {
            l.head = newnode;
        } else {
            previous.next = newnode;
        }
    }
    public static void main(String [] args) {
        List1 l1=new List1();
        l1.head = new ListNode(1, new ListNode(3,null));
        ListNode.print(l1.head);
        searchInsert(l1, 3, 5);
        ListNode.print(l1.head);
        searchInsert(l1, 1, 7);
        ListNode.print(l1.head);
        searchInsert(l1, 5, 8);
        ListNode.print(l1.head);
        // Einfuegen am Ende testen
        searchInsert(l1, 99, 9);
        ListNode.print(l1.head);
    }
}