精华内容
下载资源
问答
  • c语言归并两个有序链表

    千次阅读 2018-09-05 15:01:54
    归并有序列表L1,L2到L3,使L3有序,从小到大 xxwu */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef int ElemType; typedef struct LNode {  ...

    /**
    归并有序列表L1,L2到L3,使L3有序,从小到大
    xxwu
    */

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>

    typedef int ElemType;
    typedef struct LNode {
        ElemType data;
        struct LNode * next;
    } LNode, *LinkList;

    //初始化 尾插法 以9999退出
    LinkList initListTill(LinkList L);

    //归并两个有序链表L1,L2到L3,使L3有序
    LinkList mergeList(LinkList L1, LinkList L2, LinkList L3);

    //打印链表
    void printLNode(LinkList L);

    //初始化 尾插法 以9999退出
    LinkList initListTill(LinkList L) {
        L = (LNode *) malloc(sizeof(LNode));
        L->next = NULL;
        LNode *s, *r;
        r = L;
        int x;
        scanf("%d", &x);
        while(x!=9999) {
            s = (LNode *) malloc(sizeof(LNode));
            s->data = x;
            r->next = s;
            r = s;
            scanf("%d",&x);
        }
        r->next = NULL;
        return L;
    }

    //打印链表
    void printLNode(LinkList L){
        LinkList p = L->next;
        int i = 1;
        while(p != NULL) {
            printf("第 %d 个元素值 %d \t\t对应地址%x\n",i,p->data,p);
            p = p->next;
            i++;
        }
    }

    //归并两个有序链表L1,L2到L3,使L3有序
    LinkList mergeList(LinkList L1, LinkList L2, LinkList L3) {
        LNode *c1 = L1->next;
        LNode *c2 = L2->next;
        L3 = (LinkList)malloc(sizeof(LNode));
        LNode *till = L3;
        while(c1 && c2) {
            LNode *c3 = (LinkList) malloc(sizeof(LNode));
            if(c1->data < c2->data) {
                c3->data = c1->data;
                c1 = c1->next;
            }else{
                c3->data = c2->data;
                c2 = c2->next;
            }
            //L3尾插法
            till->next = c3;
            till = c3;
        }
        while(c1) {
            LNode *c3 = (LinkList) malloc(sizeof(LNode));
            c3->data = c1->data;
            till->next = c3;
            till = c3;
            c1 = c1->next;
        }
        while(c2) {
            LNode *c3 = (LinkList) malloc(sizeof(LNode));
            c3->data = c2->data;
            till->next = c3;
            till = c3;
            c2 = c2->next;
        }
        till->next = NULL;
        //释放L1,L2
        // free(L1);free(L2);
        return L3;
    }

    int main()
    {
        LinkList L = NULL;
        L = initListTill(L);// L地址发生了改变
        printLNode(L);
        LinkList L2 = NULL;
        L2 = initListTill(L2);// L地址发生了改变
        printLNode(L2);

        LinkList L3 =NULL;
        L3 = mergeList(L,L2,L3);
        printLNode(L3);
    //    insertElem(L2,3,555);
    //    LNode *p = getLocateElem(L2,3);
    //    printf("第3个元素%d\n",p->data);
    //    printLNode(L2);
    //    deleteLocateElem(L2,1);
    //    deleteElem(L2,p);
    //    printLNode(L2);
        return 0;
    }
     

    测试:

    展开全文
  • 归并两个有序链表

    2021-01-18 20:05:44
    构造算法归并两个链表,结果存储在新链表z中,z也按数据域的非递减序排列。在归并过程,表x和表y中的结点一一链到z中,要求不用临时结点。讨论算法的复杂度。 二、c++代码 代码如下: #include <iost

    系列文章目录

    前言

    《数据结构基础》c语言版 第2版,Ellis Horowitz著,朱仲涛译
    4.2节,page120,习题6

    一、题目描述

    令x=(x1,x2,…,xn)和y=(y1,y2,…ym)是两个链表,按数据域的非递减序排列。构造算法归并这两个链表,结果存储在新链表z中,z也按数据域的非递减序排列。在归并过程,表x和表y中的结点一一链到z中,要求不用临时结点。讨论算法的复杂度。

    二、c++代码

    代码如下:

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    
    typedef struct Node{
        int data;
        struct Node *link;
    }listNode;
    
    listNode* create_list(int length)
    {
        if(length<1)
        {
            printf("链表中没有元素!\n");
        }
        listNode *first = (listNode*)malloc(sizeof(listNode));
        first->link = NULL;
        listNode *p = first;
        int value;
        printf("请输入%d个整数:\n",length);
        for(int i=1;i<=length;i++)
        {
            listNode *temp = (listNode*)malloc(sizeof(listNode));
            scanf("%d",&value);
            temp->data = value;
            p->link=temp;
            p = temp;
        }
        p->link = NULL;
        return first;
    };
    
    listNode* merge_list(listNode *l1,listNode *l2)
    {
        listNode *new_list = new listNode;
        new_list->link = NULL;
        listNode *temp = new_list;
        listNode *temp1 = l1->link;
        listNode *temp2 = l2->link;
        while (temp1 && temp2)
        {
            if(temp1->data < temp2->data)
            {
                listNode *p = new listNode;
                p->data = temp1->data;
                temp1 = temp1->link;
                temp->link = p;
            } else{
                listNode *p = new listNode;
                p->data = temp2->data;
                temp2 = temp2->link;
                temp->link = p;
            }
            temp = temp->link;
        }
        while (temp1)
        {
            listNode *p = new listNode;
            p->data = temp1->data;
            temp->link = p;
            temp1 = temp1->link;
            temp = temp->link;
        }
        while (temp2)
        {
            listNode *p = new listNode;
            p->data = temp2->data;
            temp->link = p;
            temp2 = temp2->link;
            temp = temp->link;
        }
        return new_list;
    }
    
    void print_list(listNode* list)
    {
        listNode *tmp;
        tmp = list->link;
        if(tmp==NULL) {
            printf("链表中没有元素!\n");
            return;
        }
        while (tmp)
        {
            printf("%2d",tmp->data);
            tmp = tmp->link;
        }
    }
    
    int main() {
        listNode *x,*y,*z;
        int len1,len2;
        printf("输入链表1的长度:");
        scanf("%d",&len1);
        printf("输入链表2的长度:");
        scanf("%d",&len2);
        x = create_list(len1);
        y = create_list(len2);
        z = merge_list(x,y);
        printf("合并之后的链表为:\n");
        print_list(z);
        return 0;
    }
    

    总结

    展开全文
  • C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
  • 原题:#21_归并两个有序链表 迭代 新链表中允许重复结点存在 两个已有链表本身有序 不需要重新建立新链表 两两比较结点值的大小,较大的放到下一轮继续比较,较小的并入。 当短链表并入完成后,长链表剩下部分...

    原题:#21_归并两个有序链表

    • 迭代
      • 新链表中允许重复结点存在
      • 两个已有链表本身有序
      • 不需要重新建立新链表
      • 两两比较结点值的大小,较大的放到下一轮继续比较,较小的并入。
      • 当短链表并入完成后,长链表剩下部分直接并入
      • 时间复杂度:O(n+m)
      • 空间复杂度:O(1)
    public ListNode f(ListNode headA, ListNode headB) {
        if (headA == null) {
            return headB;
        }
        if (headB == null) {
            return headA;
        }
        ListNode h1 = null;
        ListNode h2 = h1;	//将两条链表合并到h1中
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                h2.next = headA;
                headA = headA.next;
            } else {
                h2.next = headB;
                headB = headB.next;
            }
            h2 = h2.next;
        }
        h2.next = (headA == null) ? headB : headA;
        return h1.next;	//注意h1为哑节点
    }
    

    • 递归
      • 结束条件:当某一链表为空时结束
      • 递归操作:比较A节点与B节点的值的大小,若A节点的值较小,那么将A并入,并且让A的下一节点与B比较
      • 返回值: 返回有序的一段链表
      • 时间复杂度:O(n+m)
      • 空间复杂度:O(n+m)
    public ListNode f (ListNode headA, ListNdoe headB) {
        if (headA == null)
            return headB;
        if (headB == null)
            return headA;
        if (headA.val < headB.val) {
            headA.next = f(headA.next, headB);
            return headA;
        } else {
            headB.next = f(headB.next, headA);
            return headB;
        }
    }
    

    展开全文
  • 10 归并两个有序链表

    2016-01-08 19:47:26
    现在有两个有序链表的头结点, 试图将两个链表归并到一个链表中, 是一道 很常见的一道题目思路两种思路, 一种基于循环, 一种基于递归, 后者简洁的多思路一 : 首先判断两个链表的第一个结点的大小 确定头结点, 然后...

    前言

    本博文部分图片, 思路来自于剑指offer 或者编程珠玑

    问题描述

    这里写图片描述
    现在有两个有序链表的头结点, 试图将两个链表归并到一个链表中, 是一道 很常见的一道题目

    思路

    两种思路, 一种基于循环, 一种基于递归, 后者简洁的多

    思路一 : 首先判断两个链表的第一个结点的大小 确定头结点, 然后利用一个循环进行归并, 直到归并到某一个链表末尾, 然后接上另外一个链表的剩余数据即可

    思路二 : 判断两个链表的第一个结点的大小 获取较小的结点[这里 假设是从小到大], 然后设置该节点的下一个结点为归并该节点剩余的链表 和另外的一个链表的结果, 返回该较小节点 [注意这里的递归]

    参考代码

    /**
     * file name : Test01MergeTwoList.java
     * created at : 8:28:20 PM Jun 5, 2015
     * created by 970655147
     */
    
    package com.hx.test05;
    
    public class Test01MergeTwoList {
    
        // 归并两个有序链表
        public static void main(String []args) {
            LinkedList ll01 = new LinkedList();
            LinkedList ll02 = new LinkedList();
            int max = 20;
    
            for(int i=0; i<max; i+=3) {
                ll01.add(i);
            }
            for(int i=1; i<max; i+=2) {
                ll02.add(i);
            }
    
            Node head = mergeTwoList01(ll01.first(), ll02.first());
    //      Node head = mergeTwoList02(ll01.first(), ll02.first());
    
            Node tmp = head;
            while(tmp != null) {
                Log.logWithoutLn(tmp.getData() + " ");
                tmp = tmp.getNext();
            }
    
        }
    
        // 归并两个顺序的链表
        // 先确定头结点, 更新头结点所在的链表的索引到下一个元素, 设置cur索引为头结点[单独确立头结点]
        // 开始归并  知道到达任意链表的末尾, 如果比较两个链表的当前元素, 设置cur.next为较小的元素, 然后更新该较小元素所在的链表的索引, 继续比较
        // 当遍历到某一个链表的末尾之后  设置cur.next为另一个链表的索引
        public static Node mergeTwoList01(Node first, Node first2) {
            if(first == null) {
                return first2;
            }
            if(first2 == null) {
                return first;
            }
    
            Node res = null, cur = null;
            if(first.getData() < first2.getData()) {
                res = first;
                first = first.getNext();
            } else {
                res = first2;
                first2 = first2.getNext();
            }
            cur = res;
            while(first != null && first2 != null) {
                if(first.getData() <= first2.getData() ) {
                    cur.setNext(first);
                    first = first.getNext();
                } else {
                    cur.setNext(first2);
                    first2 = first2.getNext();
                }
                cur = cur.getNext();
            }
    
            if(first == null) {
                cur.setNext(first2);
            } else {
                cur.setNext(first);
            }
    
            return res;
        }
    
        // 递归版本的合并两个有序链表
        public static Node mergeTwoList02(Node first, Node first2) {
            if(first == null) {
                return first2;
            }
            if(first2 == null) {
                return first;
            }
    
            Node res = null;
            if(first.getData() < first2.getData()) {
                res = first;
                res.setNext(mergeTwoList02(first.getNext(), first2) );
            } else {
                res = first2;
                res.setNext(mergeTwoList02(first, first2.getNext()) );
            }
    
            return res;
        }
    
    
    }
    
    

    效果截图

    这里写图片描述

    总结

    这种思路 应该在我们学习归并排序的时候, 就应该使用过吧, 因为递归处理省略了对于链表遍历的循环, 以及对于两个链表中某一个链表为空的结尾的处理[传递到了下一次方法递归来处理], 所以 看起来简洁的多

    注 : 因为作者的水平有限,必然可能出现一些bug, 所以请大家指出!

    展开全文
  • 两个有序链表的合并

    2019-03-14 11:16:17
    两个有序链表合并成一个链表,合并后的链表仍然是有序的,依次输出合并后的链表的元素值,并求出第奇数位置元素之和
  • if(pa.getData() ()){ //如果a链表的节点数值小于b链表节点的数值, a链表往后移一 p = pa; pa = pa.getNext(); }else{ //如果a链表的节点数值大于b链表的节点数值,将b中的节点取出存放在q,然后后移一 ...
  • 7-3 两个有序链表序列的合并 (15 分)

    千次阅读 2019-06-10 23:12:39
    7-3 两个有序链表序列的合并 (15 分)
  • 两个量表: 链表A:1-3-5-7-9 链表B:2-4-6-8-10 将上面的链表A和链表B合并成一个链表C,最终的顺序: 链表C:1-2-3-4-5-6-7-8-9-10 解决 使用归并排序中的合并阶段进行合并排序操作 public ...
  • 合并两个有序链表(完整代码)

    千次阅读 2018-08-23 11:41:22
    合并有序链表为一个有序链表: 第一步,先给三个链表定义三个头指针,让其指向当前比较的结点(让pc先指向la); 第二步,比较la,lb中元素大小,若pa-&gt;data&lt;=pb-&gt;data;则将pa放入lc中,...
  • 归并两个递增序列链表为一个递减有序链表 时限:1000ms 内存限制:10000K 总时限:3000ms 描述 假设有两个按元素值递增有序排列的线性表a和b,均以单链表作为存储结构,请编程实现将表a和表b归并成一个按元素值...
  • public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1==NULL) return l2; if(l2==NULL) return l1; ListNode* a=new ListNode(1); ...
  • //归并有序表La和Lb,生成新的有序表Lc //并且在归并之后删除La和Lb pa = La->next; pb = Lb->next; pre = La;//将pre作为链表合并后的新的头节点 while (pa&&pb)//la和lb任意一条链表归并完毕...
  • 合并两个有序单链表,其实就是归并排序。 归并排序:先创建一个新链表,长度是两个单链表之和。然后比较两个单链表的第一个数,把数小的放入新链表,然后指针后移一位,依次比较,当某个链表遍历完了,把另一个链表...
  • 两个有序链表合并为一个有序链表 思路: 1.必须保证两个链表为有序链表 2.在两个链表都不为空的条件下,设一个 last=null; (1)如果链表1的值小于等于链表2的值,进行循环,先放链表1的值到新链表result,...
  • 递归://递归 ListNode* MergeList(ListNode* pHead1,ListNode* pHead2) { if(pHead1 == NULL) return pHead2; else if(pHead2 == NULL) return pHead1; //新链表的头 ListNode* pNewHea
  • //如果其中有一个链表遍历完成,即可退出while while(l1!=null && l2!=null){ if(l1.val){ next.next = l1; l1 = l1.next; }else{ next.next = l2; l2 = l2.next; } next = next.next; } //当退出while后,将剩下的...
  • 题目说明 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...合成两个有序序列。只不过用递归的方式去遍历链表。 递归,把min(t1,t2),加入新链。 若t1小,...
  • 合并两个有序链表 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 /** * ...
  • void MergeListR(LNode *A,LNode *B,LNode* &C)//采用尾插法建表的链表归并 算法 (A,B为递增链表,C要求为单调不减链表) {  LNode *r=NULL;   LNode *p=A->next;  LNode *q=B->next;  C=A;  C->next=...
  • 题目:归并两个有序链表 分析:之前的归并排序使用的是额外的存储和哨兵,数据结构是数组,要达到归并效果,现在这种方法是不使用额外的存储,数据结构是链表。 一个简单的流程是如下图,可以看成递归形式,终点是...
  • """将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 """ 链表结构: ...
  • 合并两个有序链表(C语言)

    千次阅读 2019-04-26 18:54:12
    两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 解决思路 1.排列顺序为由小到...
  • 数据结构-链表-合并两个有序链表(递归详细分析实现) 题目描述 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 /*数据结构*/ ListNode { int val; ListNode *...
  • /** * @ClassName MyList * @Description: TODO * @Author ZK * @Date 2020/8/24 17:02 * @Version V1.0 **/ public class MyList { ... //若两个链表都为空,返回null if (head1 == null &am
  • 问题:将两个有序链表合并成一个有序链表 代码展示: void Merge(LinkList &P,LinkList &Q,LinkList &L) { LinkList p = P->next; LinkList q = Q->next; LinkList l = L; while(p!=NULL &...
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 题解: class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* ...
  • 两个有序链表合并为一个链表任然有序,两个链表都是从大到小或者从小到大。 方法: 1.将两个链表连起来,对所有元素进行排序。 2.因为两个链表的长度可能不同,则将两链表相同长度的一部分进行排序,将较长链表的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,338
精华内容 6,935
关键字:

归并两个有序链表