public class List1a {
    ListNode head;
    List1a(ListNode n) {
        head=n;
    }

    static void searchInsert(List1a 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;
        }
    }

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