The title

Leetcode-cn.com/problems/me…

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.

Train of thought

Create a linked list C with a double pointer to the head node AB, then compare the size of the list, place the smaller one in and move the pointer. Note:

1, dummyhead

2, boundary

3. C moves its pointer after putting a value

code

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode L3 = new ListNode(0); ListNode l3 = L3; ListNode A = l1; ListNode B = l2; while(A ! = null && B ! = null){ if(A.val <= B.val){ l3.next = A; A = A.next; } else{ l3.next = B; B = B.next; } // next = next; // next = next; // next = next; } l3.next = A == null ? B : A; return L3.next; }}Copy the code

Idea 2 — Recursion

Recursion is to figure out what this node is going to do, and what this node is going to do is:

Compare the size, then place the smaller value in the linked list, and the smaller pointer moves one step back.

Then clarify the recursive entry parameters and exit returns:

The entry argument should be two lists, and the exit return is the new list.

The exit return is wrong, because the recursion is the one that returns the smaller value

So let’s do it, don’t worry about the details, let’s do the recursion.

Actually starting to write this recursion, it’s still a little foggy

It makes sense if you look at it again. The smaller value next points to the recursive result of the rest of the result.

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){return l2; } if(l2 == null){return l1; } // The function of mergeTwolists is to merge ascending lists // when l1 is small, // return l1 if(l1.val <= l2.val){l1.next = mergeTwoLists(l1.next,l2); return l1; }else{ l2.next = mergeTwoLists(l2.next,l1); return l2; }}}Copy the code