精华内容
下载资源
问答
  • 3、将两个从小到大排列的链表合并为一个新链表(仍然有序排列),输出合并前的两个链表,输出合并后的链表,检查合并是否成功。
  • C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
  • c代码-将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
  • 该算法为将两个递增的链表合并为一个递减链表,采用头插法和尾插法两种不同的方法实现
  • 将两个有序的链表合并为一个有序链表,链表的大小是可变的
  • 链表合并

    2019-04-11 10:33:38
    已知两个链表head1和head2各自有序,请把它们合并成一个依然有序的链表。结果链表要包含head1和head2的所有结点,即结点值相同。 方法1:递归法 具体步骤如下所示: 1)比较链表1(head1)和链表2(head2)的第一个...

    描述:

    已知两个链表head1和head2各自有序,请把它们合并成一个依然有序的链表。结果链表要包含head1和head2的所有结点,即结点值相同。

    方法1:递归法

    具体步骤如下所示:

    1)比较链表1(head1)和链表2(head2)的第一个结点数据,如果head1.data<head2.data,则把结果链表头结点指向链表head1中的第一个结点。

    2)对剩余的链表head1.next和链表2(head2)再调用同样的方法,比较得到结果链表的第二个结点,添加到合并后列表的后面。

    3)一直递归调用步骤2),直到两个链表的结点都被加到结果链表中。

    代码如下:

    class Node{
        Node next=null;
        int data;
        public Node(int data){
            this.data=data;
        }
    }
    
    
    public class Test {
        public static Node mergeList(Node head1,Node head2){
            if(head1==null){
                return head2;
            }
            if(head2==null){
                return head1;
            }
            Node head=null;
            if(head1.data<head2.data){
                head=head1;
                head.next=mergeList(head1.next,head2);
            }
            else{
                head=head2;
                head.next=mergeList(head1,head2.next);
            }
            return head;
        }
    
        public static void main(String[] args) {
            Node head1=new Node(1);
            Node node3=new Node(3);
            head1.next=node3;
            Node node5=new Node(5);
            node3.next=node5;
            node5.next=null;
    
            Node head2=new Node(2);
            Node node4=new Node(4);
            head2.next=node4;
            Node node6=new Node(6);
            node4.next=node6;
            node6.next=null;
    
            Node mergeHead=mergeList(head1,head2);
            while(mergeHead!=null){
                System.out.print(mergeHead.data+" ");
                mergeHead=mergeHead.next;
            }
        }
    }

    方法二:非递归法

    在遍历两个链表过程中,改变当前链表指针的指向来把两个链表串连成一个有序的列表,实现代码如下:

    public class Test2 {
        public static Node mergeList(Node head1,Node head2){
            if(head1==null)
                return head2;
            if(head2==null)
                return head1;Node p1,p2,head;
                //确定合并后的头节点
            if(head1.data<head2.data){
                head=head1;
                p1=head1.next;
                p2=head2;
            }
            else{
                head=head2;
                p1=head1;
                p2=head2.next;
            }
            Node pcur=head;
            while(p1!=null&&p2!=null){
                //把链表head1当前遍历的结点添加到合并后链表的尾部
                if(p1.data<=p2.data){
                    pcur.next=p1;
                    pcur=p1;
                    p1=p1.next;
                }
                //把链表head2当前遍历的节点添加到合并后链表尾部
                else{
                    pcur.next=p2;
                    pcur=p2;
                    p2=p2.next;
                }
                //head2链表已经遍历结束,把head1遍历剩余的结点添加到合并后链表的尾部
                if(p1!=null){
                    pcur.next=p1;
                }
                if(p2!=null){
                    pcur.next=p2;
                }
            }
            return head;
        }
    }

     

    展开全文
  • 将两个升序链表合并,合并后还是一个升序列表,尽量用最小的时间复杂度。 思路一 两个链表合成一个链表,可以将两个链表打散,然后按照大小顺序放入到一个数组里,冒泡排序后,将节点串起来,这样就可以实现一个...

    题目

            将两个升序链表合并,合并后还是一个升序列表,尽量用最小的时间复杂度。

    思路一

            两个链表合成一个链表,可以将两个链表打散,然后按照大小顺序放入到一个数组里,冒泡排序后,将节点串起来,这样就可以实现一个升序链表。

    思路二

            思路一方法虽然可行,但是时间复杂度大于O(N2), 还重新创建了一个新数组去装这些元素, 空间复杂度也是比较大,因此方案一不可取。

            我们可以利用两个升序链表的特点: 可以按照顺序进行遍历,具体实现步骤如下:

            1)  定义一个新链表的头节点为两个链表中头节点的最小值。

     Node root=Max(l1.head.data,l2.head.data)

            2) 将剩下的两个链表,按照头头比较的规则,将值小的节点接入到新链表的尾节点, 因为每次我们就是取两个值,这两个值中肯定较小值肯定比新链表的尾节点的值要大,因此可以采用递归的思想来实现。

    什么是头头比较?

            我们每次拿出两个链表的头节点,值小的节点插入到新链表尾,然后在旧链表中删除该节点。

            3) 递归结束的条件。 当任意一个链表结束时,也就意味着遍历结束和递归结束。如果是刚好比较完,那么就返回NULL插入到新链表的尾部,如果有一个链表遍历完了,另外一个链表还多余了很多节点,那么就直接将剩余的节点插入到新链表的尾部即可,因为每次递归(比较完毕后)旧链表中剩下的值总是大于或等于新链表的最大值。
     

    import chain.ReverseList;
    
    /**
     * @decription:
     * @author: zhengbing.zhang
     * @date: 2021/7/9 10:50
     * 将两个升序链表合并,合并后还是一个升序列表,尽量用最小的时间复杂度。
     * 1->3-5>7
     * 2->4->5->8
     * 2  3  3 4
     * 1 1 2 3
     */
    public class LinkedListMerge {
    
        static Node one;
    
        static Node two;
    
        static {
            one = new Node(1, new Node(3, new Node(5, new Node(7, null))));
            two = new Node(2, new Node(4, new Node(5, new Node(8, new Node(9, null)))));
        }
    
        static class Node {
            Integer data;
            Node next;
    
            public Node(Integer data, Node next) {
                this.data = data;
                this.next = next;
            }
    
            public Integer getData() {
                return data;
            }
    
            public void setData(Integer data) {
                this.data = data;
            }
    
            // 使用递归的思想遍历链表
            public String traverse() {
                return this.getData() + "->" + (this.next == null ? "NULL" : this.next.traverse());
            }
        }
    
    
        /**
         *  定义好头节点后,因为两个链表都是升序的,我们可以把每次的操作分解为三步:  比较两个链表的头节点 ->  将小的节点插入到新链表的尾节点-> 旧链表的节点移除。
         *  递归结束的条件: 任意一个链表为空链表。
         * @param l1
         * @param l2
         * @param node
         * @return
         */
        public static Node mergeLists(Node l1, Node l2, Node node) {
            // 如果有链表先为空,那么就将另外一个链表接入到新的链表上
            if (l1 == null) {
                node.next = l2;
                return node;
            }
            if (l2 == null) {
                node.next = l1;
                return node;
            }
            // 定义好头节点后,分别比较两个链表中的元素,哪个小哪个就先插入到新链表的后面,每次插完后,删除链表节点(移到下一个节点)
            if (l1.getData() > l2.getData()) {
                node.next = new Node(l2.getData(), null);
                l2 = l2.next;
            } else {
                node.next = new Node(l1.getData(), null);
                l1 = l1.next;
            }
            return mergeLists(l1, l2, node.next);
        }
    
    
        public static void main(String[] args) {
            Node current;
            // 定义新链表的头节点
            if (one.getData() > two.getData()) {
                current = new Node(two.getData(), null);
                two = two.next;
            } else {
                current = new Node(one.getData(), null);
                one = one.next;
            }
            mergeLists(one, two, current);
            System.out.println(current.traverse());
        }
    }
    

    打印结果:

    此方法的最坏时间复杂度为o(n),如果链表的长度差距很大的话,最后可以少比较很多次。

    类似问题

            归并排序。

            上述的合并方法有点类似归并排序的思想,只不过是给的链表已经是排序好了的,归并排序的思想如下:

            1)  将数列均分成2个数列,然后分别对2个数列进行排序。

            2)  创建一个新的数列,然后使用2个指针分别指向2个数列,将相对较小的值放入到新的数列里。

            3) 将剩余的数列放入到新数列后面,然后重复上述步骤,直到排序完毕。

        public static int[] mergeSort(int[] nums, int l, int h) {
            if (l == h) {
                return new int[]{nums[l]};
    
            }
            int mid = l + (h - l) / 2;
            //左有序数组
            int[] leftArr = mergeSort(nums, l, mid);
            //右有序数组
            int[] rightArr = mergeSort(nums, mid + 1, h);
            //新有序数组
            int[] newNum = new int[leftArr.length + rightArr.length];
            int m = 0, i = 0, j = 0;
            while (i < leftArr.length && j < rightArr.length) {
                newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
            }
            while (i < leftArr.length) {
                newNum[m++] = leftArr[i++];
            }
            while (j < rightArr.length) {
                newNum[m++] = rightArr[j++];
            }
            return newNum;
        }

    扩展

            求K个升序链表的合并结果。

    思路一

            暴力破解法。 采用一个List装下所有的升序链表,然后使用排序,再将排序后的链表放入到一个链表里。

        /**
         * 扩展: k 个有序链表怎么合并
         * extension:  Merge  k sorted lists and return it as one sorted list, analyze and describe its complexity.
         * use brute force method  暴力破解法
         */
        private static Node mergeManyList(List<Node> nodeList) {
            List<Integer> numLists = new ArrayList<>();
            for (Node node : nodeList) {
                while (node != null) {
                    numLists.add(node.getData());
                    node = node.next;
                }
            }
            // 默认采用插入排序
            Collections.sort(numLists);
            Node node = new Node(numLists.get(0));
            Node head = node;
            for (int i = 1; i < numLists.size() - 1; i++) {
                head.setNext(new Node(numLists.get(i)));
                head = head.next;
            }
            return node;
        }

     思路二

            采用纵向查找的方法,定位第一个值为最小值,将后续的最小值不断的接入到链表后面即可。

            每次比较出K个链表的头节点的最小值,下标为index, 每找到一个最小的值,需要将该节点删除掉, 方法如下:

     nodeList.set(index, nodeList.get(index).next);

             最后当nodeList列表的所有链表都为空时,暂停循环。

    
        /**
         * 纵向查找, 每次找出最小的将head的next指针执行最小的元素即可。
         * @param nodeList
         * @return
         */
        private static Node mergeListNode(List<Node> nodeList) {
            Node head = new Node(Integer.MAX_VALUE);
            Node current = head;
            while (true) {
                boolean isBreak = true;
                Node min = new Node(Integer.MAX_VALUE);
                int index = -1;
                for (int j = 0; j < nodeList.size(); j++) {
                    if (nodeList.get(j) != null && nodeList.get(j).getData() < min.getData()) {
                        min = nodeList.get(j);
                        // to find the minimum index
                        index = j;
                    }
                    // stop the loop until nodeList become empty
                    if (nodeList.get(j) != null) {
                        isBreak = false;
                    }
                }
    
                if (isBreak) {
                    break;
                }
                // remove the head node in time
                nodeList.set(index, nodeList.get(index).next);
                //  add node which is minimum after  the node of current.
                head.next = min;
                head = head.next;
            }
    
            return current.next;
        }
    

    打印结果:

    展开全文
  • c语言 链表合并,排序

    千次阅读 2019-08-15 10:54:46
    要求把两个链表合并,按学号升序排列。 输入: 第一行,a、b两个链表元素的数量N、M,用空格隔开。 接下来N行是a的数据 然后M行是b的数据 每行数据由学号和成绩两部分组成 输出: 按照学号升序排列的数据 样例...

    题目描述:

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

    输入:

            第一行,a、b两个链表元素的数量N、M,用空格隔开。 接下来N行是a的数据 然后M行是b的数据 
            每行数据由学号和成绩两部分组成
    

    输出:

             按照学号升序排列的数据
    

    样例输入:

                                          2 3
                                          5 100
                                          6 89
                                          3 82
                                          4 95
                                          2 10
    

    样例输出:

                                          2 10
                                          3 82
                                          4 95
                                          5 100
                                          6 89
    

    分析:

         这个题的难点在于要熟悉链表的操作,而且要将排序和链表结合起来。我的思路是先创建链表,
         然后读取两个链表的数据,将两个链表合并成一个新的链表,然后用选择排序法将新的链表排序并输出。
    

    代码:

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct st_data
    {
        int number;
        int score;
        struct st_data *next;
    }Data,*Datap;         // 定义结构体
    
    Datap creatlist(int length)      // creatlist函数用来创建链表,传入的参数为要创建的链表的长度
    {
        Datap head;        // 定义一个头指针
        Datap q;           // 用来遍历链表
        Datap list;        // 链表的结点
        int i = 0;
    
        head = (Datap)malloc(sizeof(Data));
        head->next = NULL;  // 创建头结点
        q = head;           // 指向头结点
        for(i = 0;i < length;i++)
        {
            list = (Datap)malloc(sizeof(Data));
            scanf("%d%d",&(list->number),&(list->score));  // 创建结点,并读取数据
            q->next = list;
            q = list;        // 连接结点
        }
        q->next = NULL;
    
        return head;        // 返回头结点
    }
    
    void sort_list(Datap list1,Datap list2,int length) // sort_list函数将链表排序,传入的参数为两个链表和两个链表的长度之和
    {
        Datap temp;         // 定义一个指针,用来存放两个链表
        Datap min;          // 定义一个指针指向最小学号
        Datap nowtemp;      // 定义一个指针指向目前temp的位置
        int minnumber = 0;
        int minscore = 0;
    
        temp = list1;
        list2 = list2->next;
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = list2;
        temp = list1->next;   // 将两个链表合并存放在temp中
    
        while(temp != NULL)    // 用选择法排序,每次找出剩余最小的和前面的交换
        {
            nowtemp = temp;
            min = temp;
            min->number = temp->number;   // 先将第一个值当作最小的
            while(nowtemp != NULL)
            {
                if(nowtemp->number < min->number)
                {
                    min = nowtemp;
                }
                nowtemp = nowtemp->next;
            }       // 搜索出最小学号
            minnumber = min->number;
            min->number = temp->number;
            temp->number = minnumber;    // 将最小学号和前面的交换
            printf("%d ",temp->number);  // 输出最小学号
    
            minscore = min->score;
            min->score = temp->score;
            temp->score = minscore;      // 将最小学号的分数和前面的交换
            printf("%d\n",temp->score);  // 输出最小学号的分数
    
            temp = temp->next;             // 继续向下搜索
        }
    }
    
    int main50()
    {
        int length1 = 0;
        int length2 = 0;
        Datap list1;
        Datap list2;
    
        scanf("%d%d",&length1,&length2);
        list1 = creatlist(length1);      // 创建链表1
        list2 = creatlist(length2);      // 创建链表2
    
        sort_list(list1,list2,(length1 + length2));
        
        while(list1->next != NULL)
        {
            q = list1->next;
            free(list1);
            list1 = q;
        }
        free(list1);
        return 0;
    }
    
    
    展开全文
  • 个人资料整理 仅限学习使用 课程设计报告 课程设计题目实现两个链表合并 学生姓名 黎微微 专 业 计算机信息管理 班 级 1141301 指导教师 吴志强 2018年 01月 08 日 个人资料整理 仅限学习使用 一 课程设计目的 ...
  • 输入链表A 与B(空格分隔),说输入的数字序列可以无序 最后合并成一个有序的列表!MFC可视化编程
  • c语言链表合并(递归和非递归实现) 包括链表创建 打印输出 通过测试,可以使用 测试环境:c-free 5.0
  • 题目:两个有序链表,一个升序,一个降序,如何将两个链表合并成一个升序链表。如: 升序链表一: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
    ----合并结束-----
    
    展开全文
  • 链表合并的两种方法

    千次阅读 2020-08-05 15:57:52
    将两个递增的链表合并为一个递增的链表 方法一:递归法 递归的思想自上而下,每次取出一个最小的节点指向递归找出的下一个最小的节点。 找的时候自上而下,但是结果的合并是自下而上(递归过程呈"V"字形),因此只需将...
  • 用于数据结构中链表的归并操作,可以将连个链表的数据类型的数据合并成一个链表
  • 将两个有序链表合并为一个有序链表 思路: 1.必须保证两个链表为有序链表 2.在两个链表都不为空的条件下,设一个 last=null; (1)如果链表1的值小于等于链表2的值,进行循环,先放链表1的值到新链表result,...
  • 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [  1->4->5,  1->3->4,  2->6 ] 输出: 1->1->2->3->4->4->5->6
  • 具体思想就是新建一个链表,然后比较两个链表中的元素值,把较小的那个链到新链表中,由于两个输入链表的长度可能不同,所以最终会有一个链表先完成插入所有元素,则直接将另一个未完成的链表直接链入新链表的末尾。...
  • 多个有序链表合并成一个有序链表的C++递归实现 主体思想: 1.多个有序链表看成是一个二维链表,此二维链表在 y 轴方向是有序的,x轴方向是无序的 2.在x 轴方向(x=0),找出此维度最小的元素(可以输出了), 3....
  • 已有a、b两个链表,每个链表中的结点包括学号、成绩。要求把两个链表合并,按学号升序排列
  • if(p->next NULL){//链表为空 printf(“链表为空 !\n”); return false; } printf("\n请输入删除的位置!\n"); scanf("%i",&i); if(i){ printf(“删除位置非法 !\n”); return false; } int j=0;//让j指向的是p指向...
  • 两个升序链表合并成一个降序链表的时间复杂度

    千次阅读 热门讨论 2021-08-02 00:12:10
    【2013年统考真题】已知两个长度分别为m和n的升序链表,若将它们合并为长度为m+n的一个降序链表,则最坏情况下的时间复杂度是() A. O(n) B. O(mn) C. O(min(m,n)) D. O(max(m,n)) 答案是D 注意,此题中的时间...
  • 链表合并并排序

    千次阅读 2020-12-07 11:34:56
    将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的,且合并后新链表依然有序。 代码如下: /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class ...
  • 将两个有序链表合并,合并后的链表仍为有序链表 思路分析: 1)首先定义一个新的链表,并且将其初始化,再定义一个辅助节点cur,该节点指向新的链表的头节点mergeHead 2)循环遍历两个链表h1,h2,每次遍历时各取出一...
  • 将两个有序链表合并成一个链表

    万次阅读 多人点赞 2018-08-04 17:05:37
    代码实现功能如下:将两个有序链表合并成一个有序链表。 具体思路如下:首先自己调用链表的创建函数,手动创建两个有序链表,链表的创建以输入0作为截止标志。创建好两个有序链表之后,将两个链表的头结点进行比较...
  • 第一步当然是判空 如果其中一个链表为空 则返回另一个链表即可 要有序 所以需要比较结点大小 创建两个引用指向两个链表 同时分别创建将要合成链表的头和尾 比较两个结点的大小 将较小的结点 cur 放到新的链表...
  • 两个有序链表的去重合并
  • 两个升序链表合并为一个升序链表

    千次阅读 2020-06-29 20:04:39
    } 首先找到第一个结点较小或相等的链表记为 header1 ,while 循环找到 header1 中比 header2 要合并的数据元素大的结点的前驱结点,将 header 链表的头结点的后继结点连接到 header1 后面,继续比较header2的后继...
  • 题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出...
  • 包括定义的链表,插入数据,及输出打印 #include <iostream> #include <vector> #include <numeric> #include<algorithm> using namespace std; struct Node { int x; Node* next; Node...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 101,586
精华内容 40,634
关键字:

链表合并