JZ25 合并两个排序的链表
合并两个排序的链表
http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
双指针
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while(pHead1 && pHead2){
if (pHead1->val <= pHead2->val){
cur->next = pHead1;
pHead1 = pHead1->next;
}
else{
cur->next = pHead2;
pHead2 = pHead2->next;
}
cur = cur->next;
}
cur->next = pHead1 ? pHead1 : pHead2;
return dummy->next;
}
};
class Solution:
def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
# write code here
dummy = cur = ListNode(0)
while pHead1 and pHead2:
if pHead1.val <= pHead2.val:
cur.next = pHead1
pHead1 = pHead1.next
else:
cur.next = pHead2
pHead2 = pHead2.next
cur = cur.next
cur.next = pHead1 if pHead1 else pHead2
return dummy.next
迭代法
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if(pHead1==nullptr || pHead2 == nullptr){
return pHead1 ? pHead1 : pHead2;
}
if(pHead1->val <= pHead2->val){
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}
else{
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
};
class Solution:
def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
# write code here
if (pHead1==None): return pHead2
if (pHead2==None): return pHead1
if pHead1.val <= pHead2.val:
pHead1.next = self.Merge(pHead1.next, pHead2)
return pHead1
else:
pHead2.next = self.Merge(pHead1, pHead2.next)
return pHead2
查看3道真题和解析
