[LeetCode] 21. Merge Two Sorted Lists 合并有序链表
2023-09-27 14:28:37 时间
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
和88. Merge Sorted Array类似,数据结构不一样,这里是合并链表。
由于是链表,不能像数组一样有从后面往前写的技巧。
解法1:dummy list,新建一个链表,然后两个链表中从头各取一个元素进行比较,小的写入新链表,直到结束,返回dummy.next。
解法2:recursion,代码简洁,但空间复杂度高O(n)
Java:
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode flag = new ListNode(0); ListNode firstflag = flag; while (l1 != null && l2 != null) { if(l1.val < l2.val){ flag.next = l1; l1 = l1.next; }else { flag.next = l2; l2 = l2.next; } flag = flag.next; } flag.next = l1 != null ? l1 : l2; return firstflag.next; } }
Java:
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; } }
Python: Time: O(n), Space: O(1)
class ListNode(object): def __init__(self, x): self.val = x self.next = None def __repr__(self): if self: return "{} -> {}".format(self.val, self.next) class Solution(object): def mergeTwoLists(self, l1, l2): curr = dummy = ListNode(0) while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next curr.next = l1 or l2 return dummy.next
Python: wo
class Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ head = ListNode(0) dummy = head while l1 or l2: if l1 and l2: if l1.val < l2.val: dummy.next = l1 dummy = dummy.next # required l1 = l1.next else: dummy.next = l2 dummy = dummy.next # required l2 = l2.next elif l1: dummy.next = l1 break elif l2: dummy.next = l2 break return head.next
Python: Recursion
class Solution(object): def mergeLists(head1, head2): temp = None if head1 is None: return head2 if head2 is None: return head1 if head1.val <= head2.val: temp = head1 temp.next = mergeLists(head1.next, head2) else: temp = head2 temp.next = mergeLists(head1, head2.next) return temp
Python: Recursive, wo, Time: O(n), Space: O(n)
class Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ if not l1: return l2 if not l2: return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
Python: in-place, iteratively
def mergeTwoLists(self, l1, l2): if None in (l1, l2): return l1 or l2 dummy = cur = ListNode(0) dummy.next = l1 while l1 and l2: if l1.val < l2.val: l1 = l1.next else: nxt = cur.next cur.next = l2 tmp = l2.next l2.next = nxt l2 = tmp cur = cur.next cur.next = l1 or l2 return dummy.next
C++: Time: O(n), Space: O(1)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode dummy{0}; auto curr = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { curr->next = l1; l1 = l1->next; } else { curr->next = l2; l2 = l2->next; } curr = curr->next; } curr->next = l1 ? l1 : l2; return dummy.next; } };
C++: Recursive
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(l2->next, l1); return l2; } } };
类似题目:
[LeetCode] 23. Merge k Sorted Lists 合并k个有序链表
[LeetCode] 88. Merge Sorted Array 合并有序数组
All LeetCode Questions List 题目汇总
相关文章
- LeetCode每日一练 —— 206. 反转链表
- 【LeetCode】三数之和 [M](双指针)
- 【LeetCode】合并K个升序链表(使用优先级队列实现)
- 图解剑指 Offer II 024. 反转链表(LeetCode)
- leetCode 61.Rotate List (旋转链表) 解题思路和方法
- 2023-02-20 leetcode-3sum
- LeetCode_单调栈_中等_1019.链表中的下一个更大节点
- LeetCode_双指针_简单_234.回文链表
- LeetCode_双指针_简单_21.合并两个有序链表
- LeetCode 92 反转链表2
- leetcode 92. 反转链表 II
- LeetCode·每日一题·1019. 链表中的下一个更大节点·单调栈
- LeetCode·每日一题·1653. 使字符串平衡的最少删除次数·前缀和
- LeetCode·每日一题·809.情感丰富的文字·双指针
- Remove Duplicates from Sorted List II--LeetCode
- 【LeetCode with Python】 Rotate Image
- 【LeetCode】Counting Bits(338)
- 「LeetCode」83. 删除排序链表中的重复元素
- 「LeetCode」61. 旋转链表
- LeetCode-168. Excel表列名称(java)
- LeetCode-24. 两两交换链表中的节点(Golang实现)
- [LeetCode] 676. Implement Magic Dictionary 实现神奇字典
- [LeetCode] 86. Partition List 划分链表
- [LeetCode] 518. Coin Change 2 硬币找零 2
- [LeetCode] 142. Linked List Cycle II 链表中的环 II
- [LeetCode] 237. Delete Node in a Linked List 删除链表的节点
- [LeetCode] 138. Copy List with Random Pointer 拷贝带随机指针的链表
- leetcode 141 环形链表
- leetcode 19 删除链表的倒数第n个节点