Merge Two Sorted Lists
Problem: Merge Two Sorted Lists
We make a new reference to list node to iterate through the whole list. The reference refers to either nodes in list 1 or list 2 and we update the reference of list 1 and list 2. Don't forget to deal with lists of different length simply by attach rest of longer lists to current reference.
Code in Python:
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l = ListNode(None)
head = l
while l1 and l2:
if l1.val < l2.val:
l.next, l1 = l1, l1.next
else:
l.next, l2 = l2, l2.next
l = l.next
if l1: l.next = l1
if l2: l.next = l2
return head.next
Code in Java:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode l = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
l.next = l1;
l1 = l1.next;
} else {
l.next = l2;
l2 = l2.next;
}
l = l.next;
}
if (l1 != null)
l.next = l1;
else
l.next = l2;
return dummy.next;
}
}