LintCode 165 · Merge Two Sorted Lists.java

	/**
	* Definition for ListNode
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	/**
	* @param l1: ListNode l1 is the head of the linked list
	* @param l2: ListNode l2 is the head of the linked list
	* @return: ListNode head of linked list
	*/
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	// handle corner cases
	if (l1 == null) {
	return l2;
	}
	if (l2 == null) {
	return l1;
	}
	ListNode pre = new ListNode(-1);
	ListNode node = pre;
	ListNode left = l1;
	ListNode right = l2;
	while (left != null && right != null) {
	if (left.val < right.val) {
	node.next = new ListNode(left.val);
	left = left.next;
	} else {
	node.next = new ListNode(right.val);
	right = right.next;
	}
	node = node.next;
	}
	while (left != null) {
	node.next = new ListNode(left.val);
	left = left.next;
	node = node.next;
	}
	while (right != null) {
	node.next = new ListNode(right.val);
	right = right.next;
	node = node.next;
	}
	return pre.next;
	}
	}

view raw LintCode 165 · Merge Two Sorted Lists.java hosted with ❤ by GitHub