精华内容
下载资源
问答
  • 链表合并

    2020-07-30 17:22:26
    要求把两个链表合并,按学号升序排列。 输入 单组测试数据。 输入共三行。 第一行:输入两个正整数n和m(0< n ,m <= 100),表示链表a有n条记录,链表b有m条记录。 第二行:输入a链表的n条记录,每条记录格式为id...

    描述

    现在有a,b两个链表,每个链表中的结点包括学号,成绩。要求把两个链表合并,按学号升序排列。

    输入

    单组测试数据。

    输入共三行。

    第一行:输入两个正整数n和m(0< n ,m <= 100),表示链表a有n条记录,链表b有m条记录。

    第二行:输入a链表的n条记录,每条记录格式为id:score,分别代表学生学号和成绩,每条记录用-->隔开。

    第三行:输入b链表的m条记录。格式和a链表的一样。

    输出

    输出共一行,输出两个链表合并后并按学生id升序排列的链表。

    格式和输入的链表格式一样。

    输入样例 1

    3 2
    4:80-->3:77-->2:98
    1:99-->5:89
    

    输出样例 1

    1:99-->2:98-->3:77-->4:80-->5:89
    

    来源

    江西中医药大学OJ http://172.17.4.116

    Python

    import operator
    
    
    class Node:
        def __init__(self, pid, score):
            self.pid = pid
            self.score = score
    
    
    n, m = map(int, input().split())
    a = input()
    b = input()
    nodes = []
    arr = a.split('-->')
    brr = b.split('-->')
    for i in arr:
        pid, score = i[0], i[2:]
        node = Node(pid, score)
        nodes.append(node)
    for i in brr:
        pid, score = i[0], i[2:]
        node = Node(pid, score)
        nodes.append(node)
    cmp = operator.attrgetter('pid')
    nodes.sort(key=cmp)
    for i in nodes[:-1]:
        print(i.pid + ':' + i.score + '-->', end='')
    print(nodes[-1].pid + ':' + nodes[-1].score)
    
    
    展开全文
  • 【链表】链表合并

    2019-07-05 18:26:18
    链表合并 class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 指定一个不变的头节点 ListNode prehead = new ListNode(-1); ListNode prev = prehead; ...

    环的检测
    链表合并

    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            // 指定一个不变的头节点
            ListNode prehead = new ListNode(-1);
    
            ListNode prev = prehead;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    prev.next = l1;
                    l1 = l1.next;
                } else {
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
    
      // 返回非空
            prev.next = l1 == null ? l2 : l1;
    
            return prehead.next;
        }
    }
    复杂度分析
    
    时间复杂度:O(n + m)O(n+m) 。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, while 循环的次数等于两个链表的总长度。所有其他工作都是常数级别的,所以总的时间复杂度是线性的。
    
    空间复杂度:O(1)O(1) 。迭代的过程只会产生几个指针,所以它所需要的空间是常数级别的。
    
    
    展开全文
  • 题目:两个有序链表,一个升序,一个降序,如何将两个链表合并成一个升序链表。如: 升序链表一:1->2->3->4 降序链表二:6->5->4->3 合并后结果:1->2->3->3->4->4->5->6 ...

    题目:两个有序链表,一个升序,一个降序,如何将两个链表合并成一个升序链表。如:

    • 升序链表一:1->2->3->4
    • 降序链表二:6->5->4->3
    • 合并后结果:1->2->3->3->4->4->5->6

    思考:分成两步来实现,首先将降序链表二进行反转变成升序链表,然后就可以直接对两个升序链表进行操作了。

    实现:

    public static void main(String[] args) {
    
        System.out.println("初始化升序链表一");
        Node head1 = initHead1();
        printLinkedList(head1);
        System.out.println("-------------");
    
        System.out.println("初始化降序链表二");
        Node head2 = initHead2();
        printLinkedList(head2);
        System.out.println("-------------");
    
        //反转链表二
        Node newHead2 = reverse(head2);
    
        //合并两个升序链表
        List<Node> nodes = merge(head1, newHead2);
        for (Node node : nodes) {
            System.out.println(node.value);
        }
        System.out.println("----合并结束-----");
    
    }
    
    /**
     * 合并两个有序的链表
     *
     * @param head1 链表1的头节点
     * @param head2 链表2的头结点
     */
    private static List<Node> merge(Node head1, Node head2) {
    
        List<Node> finalList = new LinkedList<>();
    
        //循环比较两个链表的值 直到其中一个链表遍历完
        if (head1 != null && head2 != null) {
            while (head1.next != null && head2.next != null) {
                if (head1.value < head2.value) {
                    finalList.add(head1);
                    head1 = head1.next;
                } else {
                    finalList.add(head2);
                    head2 = head2.next;
                }
            }
        }
    
        //如果链表一还有值 直接赋值给新链表
        while (head1 != null) {
            finalList.add(head1);
            head1 = head1.next;
        }
    
        //如果链表二还有值 直接赋值给新链表
        while (head2 != null) {
            finalList.add(head2);
            head2 = head2.next;
        }
    
        return finalList;
    
    }
    
    /**
     * 反转链表
     *
     * @param head 头结点
     */
    private static Node reverse(Node head) {
        if (head == null) {
            return head;
        }
        Node curNode = head;
        Node nextNode;//指向下一个要执行的Node
        Node preNode = null; //指向上一个执行的Node
    
        while (curNode != null) {
            nextNode = curNode.next; //next指针后移
            curNode.next = preNode; //当前Node的指针反转
            preNode = curNode; // pre指针后移
            curNode = nextNode;//当前Node执行反转完毕,指向当前节点的指针后移
        }
        return preNode;
    }
    
    public static class Node {
        int value;
        Node next;
    
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
    
    /**
     * 初始化链表一  1->2->3->4
     */
    private static Node initHead1() {
        Node node4 = new Node(4, null);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);
        return node1;
    }
    
    /**
     * 初始化链表二 6->5->4->3
     */
    private static Node initHead2() {
        Node node4 = new Node(3, null);
        Node node3 = new Node(4, node4);
        Node node2 = new Node(5, node3);
        Node node1 = new Node(6, node2);
        return node1;
    }
    
    /**
     * 打印链表
     */
    private static void printLinkedList(Node head) {
        if (head == null) return;
        while (head != null) {
            System.out.println(head.value);
            head = head.next;
        }
    }
    

    执行结果:

    初始化升序链表一
    1
    2
    3
    4
    -------------
    初始化降序链表二
    6
    5
    4
    3
    -------------
    1
    2
    3
    3
    4
    4
    5
    6
    ----合并结束-----
    
    展开全文
  • 数据结构实验,链表合并!VC++6.0实现!MFC界面
  • 链表合并并排序

    千次阅读 2020-12-07 11:34:56
    将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的,且合并后新链表依然有序。 代码如下: /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class ...

    将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的,且合并后新链表依然有序。

    代码如下:

    /**
     * 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;
            if(l2==NULL)
                return l1;
            if(l1->val<=l2->val){
                l1->next = mergeTwoLists(l1->next,l2);
                return l1;
            }else{
                l2->next = mergeTwoLists(l1,l2->next);
                return l2;
            }
        }    
    };
    
    展开全文
  • OJ 1011 链表合并

    2020-08-07 08:59:50
    要求把两个链表合并,按学号升序排列。 输入 单组测试数据。 输入共三行。 第一行:输入两个正整数n和m(0< n ,m <= 100),表示链表a有n条记录,链表b有m条记录。 第二行:输入a链表的n条记录,每条记录...
  • 该算法为将两个递增的链表合并为一个递减链表,采用头插法和尾插法两种不同的方法实现
  • 括号匹配和链表合并mfc括号匹配和链表合并mfc括号匹配和链表合并mfc括号匹配和链表合并mfc
  • A与B链表合并成C链表(链表的归并) 已知两个有序递增A链表和B链表(非空),将两个链表合并为C链表(同为递增有序),需要我们对链表的概念有一定掌握 对节点所需条件以及节点之间建立关系有所掌握。 这个题的...
  • 利用递归思想,拼接两个链表!...//链表合并 递归方式 LIST_NODE * MergeList(LIST_NODE *m_pHead1,LIST_NODE *m_pHead2) { LIST_NODE *MergeListHead = NULL; if (m_pHead1 == NULL) { return m_pHead2; }
  • 有序链表合并

    2017-09-17 15:06:19
    有序链表合并: LA、LB是两个带头结点的有序链表,归并两个链表得到新的有序表LC。设立指针pa,pb,pc,其中pa和pb分别指向LA,LB中当前待比较的结点,pc指向LC表中当前最后一个结点。将pa,pb结点中值较小的一个...
  • 将两个有序的链表合并为一个有序链表,链表的大小是可变的
  • 两个无序链表合并成一个有序链表

    千次阅读 2019-10-18 10:04:12
    两个无序链表合并成一个有序链表 要求将两个无序链表合并成一个有序链表,要求时间复杂度不大于O(n^2),空间复杂度为O(1) 即不可以开辟新的空间存储链表,另外不可采用复制节点值的方法实现,只能通过链表节点的交换...
  • 17.12.31 链表合并

    2019-09-27 19:38:30
    链表合并 描述 定义一种单向链表,链表结点LinkNode包含一个整数和一个指向下一个节点的指针。编写下面四个子函数:1、建立链表: 从标准输入读取数据,并创建链表,返回创建的链表头LinkNode *...
  • 将两个有序链表合并成一个链表

    万次阅读 多人点赞 2018-08-04 17:05:37
    代码实现功能如下:将两个有序链表合并成一个有序链表。 具体思路如下:首先自己调用链表的创建函数,手动创建两个有序链表,链表的创建以输入0作为截止标志。创建好两个有序链表之后,将两个链表的头结点进行比较...
  • 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;2-&gt;3-&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,060
精华内容 7,224
关键字:

链表合并