Merge two sorted linked lists

Categories: [sword refers to offer]

Tags: Daily Practice

date: 2022/01/27

Merge two sorted linked lists

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

Limitations:

0 <= List length <= 1000

Source: LeetCode

Link: leetcode-cn.com/problems/he…

Method 1: iteration

Our goal is to merge two ordered lists into one ordered list, so every time we do this, we’re going to get the node that l1 points to and the node that L2 points to, which is smaller. This is true for iteration and recursion.

When using iteration

  • To treat the first node with the rest, a header is typically defined.

When you use recursion

  • We can often use the return value of a recursive function to return the first node of the processed list to the next level.

  • The next-level function directly links the return value to next on the current node.

The iteration

  • Defining headers
  • If the value of the node pointed to by L1 is less than the value of the node pointed to by L2, then l1 is linked to the next position of the end node
  • Otherwise, link L2 to the next position of the header
  • The loop continues until L1 or L2 is NULL
  • Finally, link the rest of L1 or L2 after the header
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode *head = new ListNode(0);
    ListNode *ret = head;
    while(l1 ! =NULL&& l2 ! =NULL) {
        if (l1->val < l2-> val) {
        	head->next = l1;
        	l1 = l1->next;
        } else {
            head->next = l2;
            l2 = l2->next;
        }
        head = head->next;
    }
    head->next = l1 == NULL ? l2 : l1;
	return ret->next;
}
Copy the code

Method two: recursion

The first step in writing a recursion should be to identify what the current function is supposed to do.

The functionality

  • Returns the smaller value of the node pointed to by L1 and the node pointed to by L2

  • And link the return value from the lower function to the end of the current node

End of function condition

  • When L1 is empty, or l2 is empty, the function ends

  • Returns the rest of L1 or L2

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if(! l1 || ! l2) {// List null
        return(! l2 ? l1 : l2); }if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2); / / recursion
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);	/ / recursion
        returnl2; }}Copy the code