当前位置:   article > 正文

【笔试真题】牛客真题:JZ25 合并两个排序的链表_jz25合并两个排序的链表 python

jz25合并两个排序的链表 python

这里写目录标题

题目

输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围: 0 ≤n≤1000,-1000
节点值 : −1000≤节点值≤1000
要求:空间复杂度 O(1)O(1)时间复杂度 O(n)O(n)

在这里插入图片描述

或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所以对应的输出为{-1,1,2,3,4,4},转换过程如下图所示:

在这里插入图片描述

分析

这道题,我们首先会想到的是,遍历两个链表的节点,谁的值小,就往后连.所以,这里有一个问题,要连在谁的后面呢?

由于谁的值更小是不确定的,所以,为了避免头结点不确定的情况,我们这里定义一个节点newHead1,谁的值小,就直接连在newHead后面.这样,返回头结点时,就返回newHead.next就行.

ListNode newHead = new ListNode(-1);
  • 1

之后,就谁的值小,谁就往newHead后面连即可.

由于newHead不能改变,所以定义一个tmp去把值小的节点连到后面

ListNode tmp = newHead;
     while(head1 != null && head2 != null){
         if(head1.val <= head2.val){
             tmp.next = head1;
             head1 = head1.next;
         }else{
             tmp.next = head2;
             head2 = head2.next;
         }
         tmp = tmp.next;
     }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

最后,看谁的节点还没走完,连到tmp后面即可

if(head1 != null){
    tmp.next = head1;
}
if(head2 != null){
    tmp.next = head2;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

代码

代码:GitHub

/**
 * @author hanson
 * @date 2024/3/12 22:40
 */
public class JZ25 {
    /*
     * 输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
     * 如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示:
     * */
    // 定义链表节点类
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    public static ListNode Merge(ListNode head1, ListNode head2) {
        //谁比较小,谁就是next
        //循环结束后,谁不为空,就接着往后面放
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if (head1 != null) {
            tmp.next = head1;
        }

        if (head2 != null) {
            tmp.next = head2;
        }

        return newHead.next;
    }

    public static void main(String[] args) {
        // 创建第一个链表: 1 -> 3 -> 5 -> null
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(3);
        head1.next.next = new ListNode(5);

        System.out.println("head1:");
        printList(head1);

        // 创建第二个链表: 2 -> 4 -> 6 -> null
        ListNode head2 = new ListNode(2);
        head2.next = new ListNode(4);
        head2.next.next = new ListNode(6);

        System.out.println("head2:");
        printList(head2);

        ListNode merge = Merge(head1, head2);

        System.out.println("merge:");
        printList(merge);

    }

    // 打印链表的方法
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

代码运行结果:

head1:
1 -> 3 -> 5 -> null
head2:
2 -> 4 -> 6 -> null
merge:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Process finished with exit code 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号