合并两个已排序的链表,并将其作为一个新列表返回。新列表应该通过拼接前两个列表的节点来完成。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
使用最原始的办法,定义一个头指针dummy,遍历两个链表,根据链表节点,进行连接,直到一个链表为空为止,再将dummy和剩下的一个链接起来。
public ListNode mergeTwoLists_1(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode dummy = new ListNode(0);
ListNode current_node = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current_node.next = l1;
l1 = l1.next;
} else {
current_node.next = l2;
l2 = l2.next;
}
current_node = current_node.next;
}
if (l1 == null)
current_node.next = l2;
else
current_node.next = l1;
return dummy.next;
}
ListNode* mergeTwoLists_1(ListNode* l1, ListNode* l2)
{
if(l1==NULL)return l2;
if(l2==NULL)return l1;
ListNode dummy = ListNode(0);
if(l1->val<l2->val)
{
dummy.next=l1;
l1=l1->next;
}
else
{
dummy.next=l2;
l2=l2->next;
}
ListNode *current_node=dummy.next;
while(l1!=NULL&&l2!=NULL)
{
if(l1->val<l2->val)
{
current_node->next=l1;
l1=l1->next;
}
else
{
current_node->next=l2;
l2=l2->next;
}
current_node=current_node->next;
}
if(l1==NULL)
current_node->next=l2;
else
current_node->next=l1;
return dummy.next;
}
class Solution(object):
def mergeTwoLists_1(self, l1, l2):
if not l1:
return l2
if not l2:
return l1
result = ListNode(0)
current_node = result
while (True):
if not l1:
current_node.next = l2
break
if not l2:
current_node.next = l1
break
if (l1.val < l2.val):
current_node.next = l1
l1 = l1.next
else:
current_node.next = l2
l2 = l2.next
current_node = current_node.next
return result.next
在网址中介绍了一种递归的方法,经过研究之后,发现其简单有效,将其实现出来,其方法,思路,供参考。
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;
}
}
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;
}
}
def mergeTwoLists(self, l1, l2):
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