精华内容
下载资源
问答
  • c代码-将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
  • 将两个升序链表合并,合并后还是一个升序列表,尽量用最小的时间复杂度。 思路一 两个链表合成一个链表,可以将两个链表打散,然后按照大小顺序放入到一个数组里,冒泡排序后,将节点串起来,这样就可以实现一个...

    题目

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

    思路一

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

    思路二

            思路一方法虽然可行,但是时间复杂度大于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;
        }
    

    打印结果:

    展开全文
  • 题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出...

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

    示例 1:
    输入:l1 = [1,2,4], l2 = [1,3,4]
    输出:[1,1,2,3,4,4]

    示例 2:
    输入:l1 = [], l2 = []
    输出:[]

    示例 3:
    输入:l1 = [], l2 = [0]
    输出:[0]

    题目来源:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/

    总结:

    1. 注意ListNode 的结构即可
    2. 一定要注意画图,打草稿
    3. 业精于勤荒于嬉

    2021年9月17日17:50:40

    参考代码:

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null ) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            ListNode temp = new ListNode();
            ListNode answer = temp;
            while (l1 != null && l2 != null){
                /**为什么这里是l1.val <= l2.val)?
                *因为:
                *1.重复的数也需要加入新的链表
                *2.由于是升序两个数都可以加入,这个不好说,写一个出来一看就明白了*/
                if (l1.val <= l2.val){
                    ListNode node = new ListNode(l1.val);
                    temp.next = node;
                    temp = node;
                    l1 = l1.next;
    
                    /**第二种写法:*/
    //                temp.next = new ListNode(l1.val);
    //                l1 = l1.next;
    
                } else {  //此时l2.val > l1.val
                    ListNode node = new ListNode(l2.val);
                    temp.next = node;
                    temp = node;
                    l2 = l2.next;
    
                    /**第二种写法*/
    //                temp.next = new ListNode(l2.val);
    //                l2 = l2.next;
                }
                /**第二种写法*/
    //            temp = temp.next;
            }
     //        用于可能含有的l1或者l2的剩余元素处理(升序的这是一个很重要的条件)
            if (l1 != null){
                temp.next = l1;
            }else {
                temp.next = l2;
            }
            return answer.next;
        }
    
    展开全文
  • 定时器--升序链表

    2018-10-29 10:20:21
    本资源是定时器链表。他是一个升序、双向链表。对于定时器数量比较少的话,还是可用的。 时间复杂度:插入O(n) 删除 O(1) 操作 O(1)
  • 两个升序链表合并为一个升序链表

    千次阅读 2020-06-29 20:04:39
    } 首先找到第一个结点较小或相等的链表记为 header1 ,while 循环找到 header1 中比 header2 要合并的数据元素大的结点的前驱结点,将 header 链表的头结点的后继结点连接到 header1 后面,继续比较header2的后继...
    LinkList MergeHeaderLinkList(LinkList L,LinkList P)
    {
        if(L == NULL || P == NULL)
            return L == NULL ? L : P ;
        LNode *header1,*header2,*S,*back;
        if(L->next->data <= P->next->data)
        {
            header1 = L;
            header2 = P;
            back = L;
        }else
        {
            header1 = P;
            header2 = L;
            back = P;
        }
        while(header2->next != NULL){
            while(header1->next != NULL && header1->next->data <= header2->next->data )
            {
                header1 = header1->next;
                printf("正在寻找...\n");
            }
            if(header1->next == NULL){
                printf("header1为空了\n");
                header1 ->next = header2->next;
                return back;
            }
            printf("找到比%d大的值%d\n",header2->next->data,header1->next->data);
            S = header2->next;
            header2->next = S->next;
            S->next = header1->next;
            header1->next = S;
            header1 = header1->next;
        }
        return back;
    }
    

    首先找到第一个结点较小或相等的链表记为 header1 ,while 循环找到 header1 中比 header2 要合并的数据元素大的结点的前驱结点,将 header 链表的头结点的后继结点连接到 header1 后面,继续比较header2的后继结点。直到 header2 中的结点全部比较完成为止。如果header1的后继结点为 NULL,直接将头结点后继结点连接到 header1 后面即可,不必再执行移动结点的操作。
    在这里插入图片描述

    展开全文
  • 直到其中某个链表为空了,那么就将另外一个链表的剩余部分全部插入到新链表的末尾 由于新链表是带傀儡节点的链表,最终返回新链表头节点的下一个节点即可 代码 public class Solution5 { public L

    思路

    • 创建一个新的链表用来保存合并结果,为了方便插入,使其带傀儡节点,定义一个引用tailNode,使其指向链表的末尾
    • 创建两个引用head1,head2,分别指向两个待合并的链表的第一个节点,比较head1的val和head2的val,小的一个插入到新链表末尾,更新即可
    • 直到其中某个链表为空了,那么就将另外一个链表的剩余部分全部插入到新链表的末尾
    • 由于新链表是带傀儡节点的链表,最终返回新链表头节点的下一个节点即可

    代码

    public class Solution5 {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode l3=new ListNode(0);
            ListNode head3=l3;
            ListNode tailNode=l3;
            ListNode head1=l1;
            ListNode head2=l2;
            while(head1!=null&&head2!=null){
                if(head1.val<head2.val){
                    tailNode.next=new ListNode(head1.val);
                    head1=head1.next;
                }else{
                    tailNode.next=new ListNode(head2.val);
                    head2=head2.next;
                }
                tailNode=tailNode.next;
            }
            if(head1==null){
                tailNode.next=head2;
            }else{
                tailNode.next=head1;
            }
            return head3.next;
        }
    }

     

    展开全文
  • 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->3->5, 2->4->6 输出:1->2->3->4->5->6 #include <stdio....
  • 将两个升序链表合并为一个新的升序链表并返回 解决思路 ①创建一个新链表 ②设置两个指针 (l1 , l2), 使它们分别指向两个链表的头结点. 用 l1, l2 遍历两个链表的同时, 比较两个链表的每一个结点元素的大小 将较小的...
  • struct node*creat(int m)//链表创建 { struct node*head; struct node*p,*pre; int i,n=0; p=pre=(struct node*)malloc(LEN); scanf("%d ",&p->a); for(i=0;i;i++) { n++; if(n==1) { head=...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 我们可以用递归实现这个...
  • 将两个升序链表合并为一个升序链表。 方法①:递归 struct ListNode { int val; ListNode* next; ListNode(int x):val(x),next(NULL){} }; class Solution { public: ListNode* mergeList(ListNode* l1, ...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 我的解答 这次的速度...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路分析: 1.先创建一个哑节点demmy,再定义一个临时变量temp,用于遍历链表,temp = demmy; 2.执行判断语句...
  • /* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 ... * @param list1 ListNode类 ...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] ...
  • 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* l1...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] ...
  • struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ //带头结点 //struct ListNode *p=l1->next; //struct ListNode *q=l2->next; //不带头结点 struct ListNode* l3, *t;...
  • 两个升序链表合并成一个升序链表

    千次阅读 2018-09-09 18:13:31
    //将两个升序链表和并成一个升序序列 #include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *next; }LinkNode; LinkNode* Creat_LinkList2() { int x; LinkNode* h; ...
  • } // 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可 prev->next = l1 == nullptr ? l2 : l1; return preHead->next; } }; 递归 class Solution { public: ListNode* ...
  • 将两个升序链表l1与l2合并为一个新的升序链表并输出。新链表是通过拼接给定的两个链表的所有节点组成的。 题目: 将两个升序链表l1与l2合并为一个新的升序链表并输出。新链表是通过拼接给定的两个链表的所有节点组成...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] ...
  • 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 二,解决思路 1,定义一个...
  • 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 链表的结构是: 链表可分为单向链表和双向链表。 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点...
  • * 将两个升序链表合并为一个新的升序链表并返回。 * 新链表是通过拼接给定的两个链表的所有节点组成的。 */ public class MergeTwoList { /** * 思路是新建一个带头节点的链表,然后根据比较两个节点的值得...
  • 用两种方法完成升序链表A、B的合并,并使C成为降序。 方法一:依次比较A、B的各结点,将较小的赋给C,A、B结点都赋给C后,再将C表逆序,得到降序表; 方法二:依次比较链表A、B,然后将结点赋给C表,在C中表从头...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路: 两个有序的链表,建立一个新的链表,然后定义一个头指针指向这个链表,然后循环遍历,直到有一个链表为...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] ...
  • leetCode 21题 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 迭代法 定义...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,157
精华内容 16,062
关键字:

升序链表