For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: Merging two ordered linked lists

Title source: 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.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code

Solution: Iteration

The first thing you need to know is the data structure of a linked list, and if you don’t know this, you’re not going to be able to do it.

Let me write down the code that defines the linked list.

public 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

This code is surprisingly simple. It defines a data field to hold an integer val, and then defines a pointer to another ListNode, which forms a separate list of nodes.

And then there’s sorting, and I’m sure most people can write it if it’s two arrays, but in fact the sort of a linked list is pretty much the same as sorting an array, so the forward thinking is just sort through a loop, simple and rough.

The idea is simple and the code is simple. Take a look at the simple iterative sorting code I wrote:

// Violent iteration
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode prehead = new ListNode(-1);

    ListNode prev = prehead;

    while(l1 ! =null&& l2 ! =null) {
        if (l1.val < l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }

    prev.next = l1 == null ? l2 : l1;

    return prehead.next;
}
Copy the code

Determine the size of the two linked list nodes, change the pointer, and loop until both nodes are null.

It should be noted that when the loop terminates, at most one of L1 and L2 is non-empty

Answer: Recursion

Adhering to the good habit, after finishing the problem to see the answer, the general sort of thinking is no slippery, but saw another way to write, this way to write to tell the truth, really a little not general assembly to write.

Although it is a bit shameful to say so, BUT I am so shameless, so directly said, recursive this way, usually basic do not write, suddenly suddenly asked me to write, or quite difficult.

/ / recursion
public ListNode mergeTwoLists_1(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    else if (l2 == null) return l1;
    else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        returnl2; }}Copy the code

Recursive code looks very succinct at the cost of readability.

On the other hand, recursion is something that every coder should be familiar with, though not often…

PS: I have found my weaknesses again. I am very happy to find and fill up my weaknesses in this way every day.