leetcode21-合并两个有序链表

原题

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

示例:

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

解法

思想

比较两个有序链表的头指针指向的值,取其中值更小的连接到一个哨兵节点后面,然后该链表的头指针向后移一格,继续和另一个节点的头指针比较。

leetcode21-合并两个有序链表

leetcode21-合并两个有序链表

leetcode21-合并两个有序链表

代码

/**
 * 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 virtualHead = new ListNode(0);
        ListNode cur = virtualHead;
        ListNode min;
        while(l1!=null || l2 != null){
            min = null;
            if(l1==null || l2!=null&&l1.val>=l2.val){
                min = l2;
                l2 = l2.next;
            }
            else if(l2==null || l1!=null&&l2.val>l1.val){
                min = l1;
                l1 = l1.next;
            } 
            cur.next = min;
            cur = cur.next;
        }
        return virtualHead.next;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode21-%e5%90%88%e5%b9%b6%e4%b8%a4%e4%b8%aa%e6%9c%89%e5%ba%8f%e9%93%be%e8%a1%a8/

发表评论

电子邮件地址不会被公开。