Last time we covered a few simple linked list problems, this time we will start with medium problems. The data structure of the linked lists used in this issue is as follows:

public class ListNode {
     int val;
     ListNode next;
     ListNode(intx) { val = x; }}Copy the code

2. Add two numbers

Give two non-empty linked lists to represent two non-negative integers. Their respective bits are stored in reverse order, and each node can store only one digit. If we add these two numbers together, a new linked list is returned to represent their sum (assuming that neither of these numbers begin with 0 except for the number 0). As shown in figure:

This is the second problem in Leetcode, and I’m sure you’ve done it before. Do not know when you do have found, there is about the linked list of the topic, as long as you do seriously, spend some time and thought is certain to be able to do, but always feel that something is wrong? What’s missing? It feels like the code isn’t pretty enough. Raise your hand if you feel the same way.

For this problem, we also received some fan contributions, saying that I can write the code, but it is long and not beautiful. Let’s take a look at one of the fans’ codes:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int flag=0;
    ListNode head1=l1;
    ListNode tempNode1=l1;
    ListNode tempNode2=l2;
    while(l1! =null&& l2! =null) {int tempVal=l1.val;
        l1.val=(l1.val+l2.val+flag)%10;
        flag=(tempVal+l2.val+flag)/10;
        tempNode1=l1;
        tempNode2=l2;
        l1=l1.next;
        l2=l2.next;
    }
    if(l1==null&& l2! =null) {while(flag! =0) {int tempVal=l2.val;
            l2.val=(l2.val+flag)%10;
            flag=(tempVal+flag)/10;
            if(l2.next==null&& flag! =0)
                l2.next=new ListNode(0);
            l2=l2.next;
        }
        tempNode1.next=tempNode2.next;
    }
    if(l2==null&& l1! =null) {while(flag! =0) {int tempVal=l1.val;
            l1.val=(l1.val+flag)%10;
            flag=(tempVal+flag)/10;
            if(l1.next==null&& flag! =0)
                l1.next=new ListNode(0); l1=l1.next; }}if(l2==null && l1==null&& flag! =0){
        tempNode1.next=new ListNode(0);
        tempNode1.next.val=(tempNode1.next.val+flag)%10;
    }
    return head1;
}
Copy the code

After a brief analysis, we find that the first while loop is the main logic, and the addition is assigned to L1, complete with carry and everything. The last three are dealing with whether L1 is longer, L2 is longer, or l1 is the same as L2. We found that this process is a normal thinking, there is no problem [consider the main logic first, then deal with the special case], but there are redundancies in the three IFs. Can we optimize the algorithm and merge the three redundancies? You can! The code is as follows:

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    int carry = 0;
    while(l1 ! =null|| l2 ! =null|| carry ! =0) {
        int val1 = l1 == null ? 0 : l1.val;
        int val2 = l2 == null ? 0 : l2.val;
        int num = val1 + val2 + carry;
        if (num < 10) {
            carry = 0;
        }
        if (num >= 10) {
            carry = 1;
            num = num % 10;
        }
        p.next = new ListNode(num);
        p = p.next;
        l1 = l1 == null ? null : l1.next;
        l2 = l2 == null ? null : l2.next;
    }
    return dummy.next;
}
Copy the code

This code starts with a new node, that is, it does not operate on the original list, but creates a new list as the final linked list. One of the things that this problem tells us is that sometimes it’s easier to use a new list.

86. Split linked lists

Given a linked list and a particular value x, separate the list so that all nodes less than x precede nodes greater than or equal to x. You should preserve the initial relative position of each node in the two partitions. As shown in figure:

This problem will be very simple and clear with the new linked list. Iterate through the old list, place the numbers less than x in a new list small, place the numbers greater than or equal to x in a new list BIG, then join them, and finally do the boundary processing. The code is as follows:

public ListNode partition(ListNode head, int x) {
    ListNode smallerHead = new ListNode(0);
    ListNode biggerHead = new ListNode(0);
    ListNode smaller = smallerHead, bigger = biggerHead;
    while(head ! =null) {
        if (head.val < x) {
            smaller = smaller.next = head;
        } else {
            bigger = bigger.next = head;
        }
        head = head.next;
    }
    smaller.next = biggerHead.next;
    bigger.next = null;
    return smallerHead.next;
}
Copy the code

You don’t want to think that using a new list is a bad idea, because space isn’t really that valuable, unless they specifically say you have to operate on the original list. After all, code is meant to make people comfortable, not computers comfortable.

Tomorrow we’ll bring you some of the worst problems in lists, the back and forth between nodes, like the advanced version of reverse lists, or rearrange lists, or sort lists.

Pay attention to the public number, more algorithm knowledge points to tell you.