Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to mix and insert ordered linked list in C++". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn how C++ can mix and insert ordered linked lists.

Merge Two Sorted Lists mixed insert ordered 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.

Example:

Input: 1-> 2-> 4, 1-> 3-> 4

Output: 1-> 1-> 2-> 3-> 4-> 4

This mixed insert ordered list is very similar to my previous article on mixed insert ordered array Merge Sorted Array, except that the data structure is changed from array to linked list, and the code is more concise. The specific idea is to create a new linked list, and then compare the values of the elements in the two linked lists, and link the smaller one to the new linked list. Because the length of the two input linked lists may be different, eventually one of the linked lists will finish inserting all the elements first. Then another unfinished linked list is directly linked to the end of the new linked list. The code is as follows:

C++ solution one:

Class Solution {public: ListNode* mergeTwoLists (ListNode* L1, ListNode* L2) {ListNode* dummy = new ListNode (- 1), * cur = dummy; while (L1 & & L2) {if (L1-> val)

< l2->

Val) {cur- > next = L1; L1 = L1-> next;} else {cur- > next = L2; L2 = L2-> next;} cur = cur- > next;} cur- > next = L1? L1: L2; return dummy- > next;}}

Java solution 1:

Public class Solution {public ListNode mergeTwoLists (ListNode L1, ListNode L2) {ListNode dummy = new ListNode (- 1), cur = dummy; while (L1! = null & & L2! = null) {if (l1.val)

< l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 != null) ? l1 : l2; return dummy.next; }} 下面我们来看递归的写法，当某个链表为空了，就返回另一个。然后核心还是比较当前两个节点值大小，如果 l1 的小，那么对于 l1 的下一个节点和 l2 调用递归函数，将返回值赋值给 l1.next，然后返回 l1；否则就对于 l2 的下一个节点和 l1 调用递归函数，将返回值赋值给 l2.next，然后返回 l2，参见代码如下： C++ 解法二： class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->

Val

< l2->

Val) {L1-> next = mergeTwoLists (L1-> next, L2); return L1;} else {12-> next = mergeTwoLists (L1, 12-> next); return L2;}

Java solution II:

Public class Solution {public ListNode mergeTwoLists (ListNode L1, ListNode L2) {if (L1 = = null) return L2; if (L2 = = null) return L1; if (l1.val)

< l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }} 下面这种递归的写法去掉了 if 从句，看起来更加简洁一些，但是思路并没有什么不同： C++ 解法三： class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; ListNode *head = l1->

Val

< l2->

Val? L1: L2; ListNode * nonhead = L1-> val

< l2->

Val? L2: L1; head- > next = mergeTwoLists (head- > next, nonhead); return head;}}

Java solution 3:

Public class Solution {public ListNode mergeTwoLists (ListNode L1, ListNode L2) {if (L1 = = null) return L2; if (L2 = = null) return L1; ListNode head = (l1.val

< l2.val) ? l1 : l2; ListNode nonhead = (l1.val < l2.val) ? l2 : l1; head.next = mergeTwoLists(head.next, nonhead); return head; }} 我们还可以三行搞定，简直丧心病狂有木有！ C++ 解法四： class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1 || (l2 && l1->

Val > L2-> val) swap (L1, L2); if (L1) L1-> next = mergeTwoLists (L1-> next, L2); return L1;}}

Java solution 4:

Public class Solution {public ListNode mergeTwoLists (ListNode L1, ListNode L2) {if (L1 = = null | | (L2! = null & & l1.val > l2.val) {ListNode t = L1; L1 = L2; L2 = t;} if (L1! = null) l1.next = mergeTwoLists (l1.next, L2); return L1 }} at this point, I believe you have a better understanding of "how C++ can mix and insert ordered linked lists". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.