Merge the two ordered lists into a new ordered list and return. The new linked list is composed of all the nodes of a given two linked list.
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Examples:
Input: 1 - > 2 - > 4, 1 - > 3 - > 4 Output: 1 - > 1 - > 2 - > 3 - > 4 - > 4
Ideas for solving problems:
Iteration and recursion can solve problems. It is just to compare the values of each node of the two linked lists in turn, take out the nodes with smaller values and add them to the end of the new list. Then continue comparing the two lists until one of them has completed traversal, when all the remaining nodes of the other list are added directly to the new list. Its logic is:
Original list: 1 - > 2 - > 4 - > null, 1 - > 3 - > 4 - > 5 - > 6 - > null Comparing the node values in turn, each header node is taken out: 1 = 1 Take out a node 1 with the same value and form a new linked list:1 At this time, the original list: 2 - > 4 - > null, 1 - > 3 - > 4 - > 5 - > 6 - > null
Contrast Header Node Value: 2 > 1 Remove 1 node and add it to the end of the new list: 1 - > 1 At this time, the original list: 2 - > 4 - > null, 3 - > 4 - > 5 - > 6 - > null
Contrast Header Node Value: 2 < 3 Remove 2 nodes and add them to the end of the new list: 1 - > 1 - > 2 At this time, the original list: 4 - > null, 3 - > 4 - > 5 - > 6 - > null
By analogy, until one of the original lists is empty-time:
Original list: null, 4 - > 5 - > 6 - > null New list: 1 - > 1 - > 2 - > 3 - > 4 When one of the original lists is empty, add another to the end of the new list directly. 1->1->2->3->4->4->5->6->null
Iterative method:
Iterative method needs to pay attention to: first determine whether the original list is empty; compare the size of the first node value of the original list, select a smaller one as the head node of the new list. Only then can it be executed according to the above logic.
If a virtual node is added as the header node, the above conditions are not required, but the next node of the virtual node should be returned.
Java:
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(-1);//New Virtual Header Node ListNode cur = head;//The current node points to the virtual header node while (l1 != null && l2 != null) {//The loop condition is that the list is not empty if (l1.val < l2.val) {//Compare the size of the value of the header node cur.next = l1;//The current node connects to one with a smaller node value l1 = l1.next;//Refresh the original list header node cur = cur.next;//Refresh the current node } else { cur.next = l2; l2 = l2.next; cur = cur.next; } } if (l1 == null) cur.next = l2;//Select another original list that is not empty and connect to the end of the new list else cur.next = l1; return head.next;//Returns the next node of the virtual header node, the real header node. } }
Python3:
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: head = ListNode(-1) cur = head; while l1 and l2: if l1.val <= l2.val: cur.next = l1 cur = cur.next l1 = l1.next else: cur.next = l2 cur = cur.next l2 = l2.next if l1: cur.next = l1 else: cur.next = l2 return head.next
Recursive method:
The recursive baseline condition is that one of the original linked lists encounters empty nodes. The return value is: the head node of the remaining part of the other list.
The size of the value of the header node is determined recursively, and the small nodes are added to the new list. Remaining list is returned to recursive function.
Java:
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2;//Baseline conditions if (l2 == null) return l1;//Baseline conditions ListNode head; if (l1.val <= l2.val) {//Select nodes with smaller node values head = l1;//Refresh header node head.next = mergeTwoLists(l1.next, l2);//Remaining list as parameter input recursive function } else { head = l2; head.next = mergeTwoLists(l1, l2.next); } return head; } }
Python3:
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 if not l2: return l1 if l1.val <= l2.val: head = l1 head.next = self.mergeTwoLists(l1.next, l2) else: head = l2 head.next = self.mergeTwoLists(l1, l2.next) return head
Welcome to Weixingong. Public Name: Love to Write Bug
