Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null && l2 == null) return null; if(l1 == null) return l2; if(l2 == null) return l1; return merge(l1,l2); } public ListNode merge(ListNode l1, ListNode l2){ ListNode fakehead = new ListNode(0); ListNode p = fakehead; while(l1!=null && l2!=null){ if(l1.val < l2.val){ p.next = l1; l1 = l1.next; } else{ p.next = l2; l2 = l2.next; } p = p.next; } if(l1 != null)//if one node is null p.next = l1; if(l2 != null) p.next = l2; return fakehead.next; } }
mistakes: when l1 or l2 to be null, make another if to connect p to existing list
learned: when merge two lists, make a fake head and a fake pointer to do connection
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null && l2 == null) return null; if(l1 == null) return l2; if(l2 == null) return l1; ListNode p = l1; ListNode q = l2; if(p.val < q.val){ p.next = mergeTwoLists(p.next,q); return p; } else{ q.next = mergeTwoLists(p,q.next); return q; } } }
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // Start typing your Java solution below // DO NOT write main() function ListNode head = new ListNode(-100); head.next = l1; merge2List(head, l2); return head.next; } public void merge2List(ListNode head, ListNode q){ ListNode p = head.next; ListNode prev = head; if( p == null) head.next = q; while(p!=null && q!=null){ if(p.val < q.val){ if(p.next != null){ prev = p; p = p.next; } else{ p.next = q; break;//very important here to exit the loop! } } else{//insert q before p ListNode temp = q.next;; prev.next = q; q.next = p; prev = q;//move forward q = temp; } } } }