题目

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.

思路

为了不多占用内存，直接利用l1和l2的空间。比较l1和l2的值，小的加入结果链表，然后继续后移链表比较。

代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = NULL; ListNode* next = NULL; if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; } head = (l1->val <= l2->val) ? l1:l2; if (l1->val <= l2->val) { head = l1; l1 = l1->next; } else { head = l2; l2 = l2->next; } next = head; while (true) { if (l1 == NULL) { next->next = l2; return head; } if (l2 == NULL) { next->next = l1; return head; } if (l1->val <= l2->val) { next->next = l1; next = next->next; l1 = l1->next; } else { next->next = l2; next = next->next; l2 = l2->next; } } return head; } };