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、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-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 ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public 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所以直接返回头指针的下一个节点
    }
}

Python版本:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param l1 ListNode类 
# @param l2 ListNode类 
# @return ListNode类
#
class Solution:
    def mergeTwoLists(self , l1 , l2 ):
        # write code here
        if l1 == None: return l2#如果l1为空返回l2
        if l2 == None: return l1#如果l2为空返回l1
        res = ListNode(-1)#创建res链表用于返回最终结果链表
        pre = res#pre的作用是进行链表的合并
        while l1 != None and l2 != None:
            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指针移动到下一个
        if l1 == None:#将不为空的那个没有遍历完的链表部分直接插入
            pre.next = l2
        else:
            pre.next = l1
        return res.next#因为头指针为-1所以直接返回头指针的下一个节点