This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

The title

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]Copy the code

Example 2:

Input: L1 = [], L2 = [] output: []Copy the code

Example 3:

Input: L1 = [], L2 = [0] output: [0]Copy the code

Tip:

  • The number of nodes in two linked lists ranges from[0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2All pressNondecreasing orderarrangement

knowledge

  • The list
  • recursive

My answer

ListNode data structure

    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(a) {}public ListNode(int val) {
            this.val = val;
        }
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next; }}Copy the code

Concrete answers

Linked list related problems, in general, are done recursively. If we use recursion in this problem, we can find the end of recursion more clearly, which is l1 or L2 is empty. The linked list is then rebuilt based on the size of its nodes.

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            printIndent(count++);
            System.out.println("l1 =" + l1.val + " l2=" + l2.val);
            l1.next = mergeTwoLists(l1.next, l2);
            printIndent(count--);
            System.out.println("l1 =" + l1.val + " l2=" + l2.val);
            return l1;
        } else {
            printIndent(count++);
            System.out.println("l1 =" + l1.val + " l2=" + l2.val);
            l2.next = mergeTwoLists(l1, l2.next);
            printIndent(count--);
            System.out.println("l1 =" + l1.val + " l2=" + l2.val);
            returnl2; }}Copy the code

Recursion topic plus this method, can print out the recursion tree, more convenient problem solving and debugging.

    /** * printIndent the ** used to print recursive trees@paramThe layer number of n *@date20:31 2021/3/9 * /
    static void printIndent(int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(""); }}Copy the code
    public static void main(String[] args) throws ParseException {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        l1.next.next.next = new ListNode(6);
        l1.next.next.next.next = new ListNode(7);
        l1.next.next.next.next.next = new ListNode(8);
        l1.next.next.next.next.next.next = new ListNode(9);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(9);
        mergeTwoLists(l1, l2);
        }
Copy the code

conclusion

No summary, this problem can be printed by human brain stack + console.