Saturday, March 16, 2013

[LeetCode] Merge Two Sorted Lists, Solution

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.
» Solve this problem

[Thoughts]

[Code]
``````1:    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
2:      if(l1 == NULL) return l2;
3:      if(l2 == NULL) return l1;
4:      ListNode *head = new ListNode(-1);
5:      ListNode *p = head;
6:      while(l1 != NULL && l2!=NULL)
7:      {
8:          if(l1->val < l2->val)
9:          {
10:             p->next = l1;
11:             l1= l1->next;
12:          }
13:          else
14:          {
15:             p->next = l2;
16:             l2 = l2->next;
17:          }
18:          p = p->next;
19:      }
20:      if(l1 != NULL)
21:          p->next = l1;
22:      if(l2 != NULL)
23:          p->next = l2;
24:      p = head->next;
25:      delete head;
26:      return p;
27:    }
``````

Update 04/13/13 refactor code for succinct
``````1:       ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
2:            ListNode* head = new ListNode(-1);
3:            ListNode* p = head;
4:            while(l1!=NULL || l2!= NULL)
5:            {
6:                 int val1 = l1==NULL?INT_MAX:l1->val;
7:                 int val2 = l2==NULL? INT_MAX:l2->val;
8:                 if(val1<=val2)
9:                 {
10:                      p->next = l1;
11:                      l1=l1->next;
12:                 }
13:                 else
14:                 {
15:                      p->next = l2;
16:                      l2 = l2->next;
17:                 }
18:                 p= p->next;
19:            }
20:            p = head->next;
21:            delete head;
22:            return p;
23:       }
``````