leetcode 21. Merge Two Sorted Lists

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.

Seen this question in a real interview before? Yes

简单的归并排序，不说了，直接上代码：

/** * 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) { if(l1==null && l2==null) return l1; ListNode p=l1; ListNode q=l2; ListNode head=new ListNode(-1); ListNode next=head; // p q 值得是当前的位置上的结点 while(p!=null && q!=null) { if(p.val < q.val) { next.next=new ListNode(p.val); next=next.next; p=p.next; } else if(p.val > q.val) { next.next=new ListNode(q.val); next=next.next; q=q.next; }else { next.next=new ListNode(p.val); next=next.next; next.next=new ListNode(q.val); next=next.next;; p=p.next; q=q.next; } } if(p!=null) next.next=p; if(q!=null) next.next=q; return head.next; } public static void main(String[] args) { Solution so=new Solution(); so.mergeTwoLists(null, null); } }

下面是C++的做法，直接归并即可。

代码如下：

#include <iostream> #include <stack> using namespace std; /* struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(-1); ListNode* a=head; while (l1 != NULL && l2 != NULL) { if (l1->val < l2->val) { a->next = new ListNode(l1->val); l1 = l1->next; a = a->next; } else { a->next = new ListNode(l2->val); l2 = l2->next; a = a->next; } } while (l1 != NULL) { a->next = new ListNode(l1->val); l1 = l1->next; a = a->next; } while (l2 != NULL) { a->next = new ListNode(l2->val); l2 = l2->next; a = a->next; } return head->next; } };