This is the 17th day of my participation in the August Text Challenge.More challenges in August

Topic describes

Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.

Example 1: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 Limit: 0 <= list length <= 1000 source: LeetCode Link: https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This is a linked list topic. Linked lists are connected by Pointers. Linked lists can easily delete and insert data in O(1) time.
  • L1 and L2 are both incremental linked lists. By using this feature, the idea can be simplified and the next node can be directly iterated.
  • In the recursive solution, if l1 is less than L2, the next node should be L1 and return l1. Before return, specify that the next node of L1 should be the combined head of l1.next and L2. Similarly, the value of L1 node is greater than l2.
  • In the iterative solution, sentinel nodes are defined, which makes it easier to return to the merged list at the end. This operation is common for linked list problems, so learn more about it.

Through the code

  • The recursive method
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode mergeTwoLists(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
  • Iterative method
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        ListNode ans = new ListNode(-1);
        ListNode current = ans;
        while(l1 ! =null&& l2 ! =null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        if(l1 ! =null) {
            current.next = l1;
        }
        if(l2 ! =null) {
            current.next = l2;
        }
        returnans.next; }}Copy the code

conclusion

  • The time complexity of this algorithm is O(n), the space complexity is O(n).
  • Adhere to the algorithm of the day, come on!