1. 合并链表
题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
原code:
时间复杂度:O(m+n)
力扣题解思路;
1.简单的递归
class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
时空都是O(m+n)//不是尾递归,会有累计的递归栈
2. 迭代实现
用虚节点假装构建新链表
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);//虚节点
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;//给虚链表连接已有节点
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
return prehead.next;
}
}
2. 第k个语法符号
思路,位运算和递归的运用
巧妙的点:非pow(2,n)求2^n,而是借助1<<n从而快速算出2^n
取非也可不用!而是^1,位运算效率能高出不少
使用位运算修改过的代码: