NC33 合并有序链表

NC33 合并有序链表

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d?tpId=117&&tqId=34954&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

-3、 设计思想：

详细操作流程看下图：

-5、代码：
c++版本:

 /**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // write code here
        if(l1 == NULL) return l2; //如果l1为空返回l2
        if(l2 == NULL) return l1;//如果l2为空返回l1
        ListNode *res = new ListNode(-1);//创建res链表用于返回最终结果链表
        ListNode *pre = res;//pre的作用是进行链表的合并
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){ //如果l1.val < l2.val 就让当前l1节点进入res
                pre->next = l1;
                l1 = l1->next;
            }else{//如果l1.val > l2.val 就让当前l2节点进入res
                pre->next = l2;
                l2 = l2->next;
            }
            pre = pre->next;//pre指针移动到下一个
        }
        pre->next = l1 == NULL?l2:l1;//将不为空的那个没有遍历完的链表部分直接插入
        return res->next;//因为头指针为-1所以直接返回头指针的下一个节点
    }
};

Java版本：

import java.util.*;

/*
 * public class ListN