链表专题—LeetCode 21. Merge Two Sorted Lists

题目链接

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.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

解题思路

1、设有头结点指针head1，head2分别对应两个链表 2、从头结点开始依次比较结点值 3、如果head1的值小于等于head2，则将head1加入到新链表并向后移动一位，否则head2加入新链表并向后移动一位 4、重复3操作直至有一个链表达到尾结点 5、将剩余的链表结点直接放入新链表

代码

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(0); ListNode* p = head; while (l1 != NULL && l2 != NULL){ int x = (l1->val <= l2->val) ? l1->val : l2->val; ListNode* new_node = new ListNode(x); p->next = new_node; p = p->next; (l1->val <= l2->val) ? l1 = l1->next : l2=l2->next; } p->next = (l1 == NULL) ? l2 : l1; return head->next; } };