Leetcode.windliang. cc/ first available

Topic Description (Medium Difficulty)

It’s just adding two lists of numbers, so you can add two really big numbers, and you don’t have to worry about int float.

Because of their own implementation is very messy, directly according to the explanation of the answer.

graphic

The left-hand side of the list is the units digit, which means 342 + 465 =807.

Train of thought

First of all, if you add each digit, you’re going to get a carry, which we’ll call carry. The most that can be carried is 1, because the most that can be done is 9 + 9 + 1 = 19, which is to add the two largest numbers and add the digits, so that the most that can be carried is 19, and there is no carry 2. Here’s the pseudocode.

  • Initialize a node’s head, dummy head, which does not store numbers. And point curr to it.
  • Initialize carry to 0.
  • Initialize p and q to be the ones bits, respectively, of the given two linked lists L1 and L2.
  • Loop until l1 and L2 both reach null.
    • Set x to the value of the p node, or 0 if p has reached null.
    • Set y to the value of q, or 0 if q has reached null.
    • Set sum = x + y + carry.
    • Update carry = sum / 10.
    • Create a node with the value sum mod 10 and point curr’s next to it, with the curr pointing to the current new node.
    • Move p and q forward.
  • Determine whether carry is equal to 1. If it is, add a node of 1 to the end of the linked list.
  • Return the dummy head’s next, where the units digit begins.

The initialized dummy head node stores no value and returns dummy Head’s next. This has the advantage of not having to change the value of the head alone. If you start with head as the units digit, you don’t know what its value is at the beginning of the initialization, so you need to correct it separately before entering the loop, rather than just using one loop.

code

class ListNode {
	int val;
	ListNode next;
	ListNode(intx) { val = x; }}public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while(p ! =null|| q ! =null) {
        intx = (p ! =null)? p.val :0;
        inty = (q ! =null)? q.val :0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if(p ! =null) p = p.next;
        if(q ! =null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}
Copy the code

Time complexity: O (Max (m, n)), where m and n represent the lengths of L1 and L2.

Space complexity: O (Max (m, n)), where m and n represent the lengths of L1 and L2. In fact, the maximum length of the new List is O (Max (m, n)) + 1, because our head stores no value.

extension

What if the linked list is stored in reverse order?

So the first thing I think about is that the list goes backwards, and then I reverse the result, which is what we had before. I don’t know if there’s another way to do it. The next analysis of the single – linked list reverse thinking.

Iterative thoughts

Let’s take a look at the original linked list.

There are two Pointers to add, pre and Next.

Initialize pre to NULL.

Then there are the steps of iteration, four in all, one in the right order.

  • Next points to next of head to prevent the original list from being lost

  • Head next is removed from the original list and points to Pre.

  • The pre pointing in the direction of the head

  • The head toward the next

One iteration is done, and if you do another iteration it looks like this.

As you can see, the whole process is simply to remove the head from the old list and add a new one to it. How do I write the code?

next = head -> next; // Save next of the head in case it is lost when the head is removed
head -> next = pre; // Remove the head from the original list and add it to the new list
pre = head;/ / the pre moves to the right
head = next; / / the head moves to the right
Copy the code

And then we have the stop condition, and we go through the loop again.

Notice that we can stop when head or next point to null. If you return the pre, it’s the reverse list.

Iteration code

public ListNode reverseList(ListNode head){
    	if(head==null) return null;
    	ListNode pre=null;
    	ListNode next;
    	while(head! =null){
    		next=head.next;
    		head.next=pre;
    		pre=head;
    		head=next;
    	}
    	return pre;
    }
Copy the code

Recursive thought

  • ListNode reverseListRecursion(ListNode head), passes in the list head and returns the reverse list head.

  • And then we figure out how to make the problem smaller step by step, and we can think of it this way.

    Take the head out, and then we call reverseListRecursion to reverse the rest, and then we put the head at the end of the new list. That’s the whole idea of recursion.

    ​

    • Take the head out

    • The rest calls reverseListRecursion and gets Newhead

    • Point 2 to 1, 1 to null, and return newhead.

  • Find the recursive exit

    Of course, if the number of nodes is one, then the reverse order is still the same, just return. How do you tell if there’s one node? If next equals null, it is one. If null is passed in, next returns an error. If null is passed in, next returns null.

code

public ListNode reverseListRecursion(ListNode head){ 
    	ListNode newHead;
    	if(head==null||head.next==null) {return head;
    	}
    	newHead=reverseListRecursion(head.next); //head.next as the header pointer for the rest
    	head.next.next=head; //head. Next represents the end of the new list. If you set next to head, add head to the end.
    	head.next=null;
    	return newHead;
    }
Copy the code