每天一道leetcode21-合并两个有序链表

乔戈里

发布于 2019-09-17 14:53:52

3560

发布于 2019-09-17 14:53:52

文章被收录于专栏：Java那些事

题目

leetcode21-合并两个有序链表

中文链接：

https://leetcode-cn.com/problems/merge-two-sorted-lists/

英文链接：

https://leetcode.com/problems/merge-two-sorted-lists/

题目详述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4输出：1->1->2->3->4->4

题目详述

思路

合并两个有序链表，由于两个链表是有序的，那么就依次去比较两个链表的当前节点的大小；首先新建一个头结点temp，用来代表一个新的链表的头结点。
链表A和B，链表A的当前节点是节点A1，链表B的当前的节点是节点B1，然后去比较A1与B1的大小，如果A1比B1小，那么temp的下一个节点就指向A1,同时链表A往下移动一个节点；
如果比较A1与B1的大小，发现A1比B1大，那么temp的下一个节点就指向B1，同时链表B往下移动一个节点；
直到链表A或者链表B当中的一个链表为空了，那么循环结束。
最后比如说链表A为空了，那么B可能不为空，所以temp的下一个节点指向B，这样就把剩余的B的节点接在了后面；
最后如果链表B为空了，那么A可能不为空，所以temp的下一个节点指向A，这样就把剩余的A链表的节点接在了temp的后面

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(-1);
        ListNode result = temp;
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                temp.next = l1;
                l1 = l1.next;
                temp = temp.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
                temp = temp.next;
            }
        }
        if(l1 == null)
            temp.next = l2;
        if(l2 == null)
            temp.next = l1;
        return result.next;

    }
}

代码讲解