精华内容
下载资源
问答
  • 两个有序链表的合并

    2019-03-14 11:16:17
    两个有序的链表合并成一个链表,合并后的链表仍然是有序的,依次输出合并后的链表的元素值,并求出第奇数位置元素之和
  • 两个有序链表的合并要求给定两个有序链表,将两个链表合并为一个有序链表思路对于给定的链表l1和链表l2。定义一个链表l3来存储合并后的两个链表。定义两个指针,分别指向两个链表的头结点,在两个链表都不为空时,...
    809282a03c89e8790cc0675131d84bee.png

    两个有序链表的合并

    要求

    • 给定两个有序链表,将两个链表合并为一个有序链表

    思路

    • 对于给定的链表l1和链表l2。定义一个链表l3来存储合并后的两个链表。
    • 定义两个指针,分别指向两个链表的头结点,在两个链表都不为空时,比较两个链表结点的值的大小。若链表l1的节点大于l2的节点,则将l1的节点值赋值给l3。l1的指针指向下一个节点。反之,则则将l2的节点值赋值给l3。l2的指针指向下一个节点。
    • 两个链表出现一个为空时,判断哪个不为空,将该链表剩下的节点全部赋值给l3。

    图解

    e7b685d432816767a2ed2d9430535e5e.png

    两个有序链表的合并


    代码

    #include #include //构造结构体typedef struct list{int data;struct list *next;}*List,LNode;//函数声明List init_list(List head,int num);void print_list(List head);List merge(List l1,List l2);void main(){    List l,l1,l2;    l1 = (LNode*)malloc(sizeof(LNode));    l1 = init_list(l1,3);    l2 = (LNode*)malloc(sizeof(LNode));    l2 = init_list(l2,7);    l = merge(l1,l2);    print_list(l);}//两个有序链表合并函数/*List merge(List l1,List l2){    List head,p,s;    head = (List)malloc(sizeof(LNode));    p = head;    while(l1 != NULL && l2 != NULL)    {        s = (List)malloc(sizeof(LNode));        if(l1->data > l2->data)        {            s ->data = l2->data;            l2 = l2->next;        }else{            s ->data = l1->data;            l1 = l1->next;        }        s->next = NULL;        p->next = s;        p = p->next;    }    while(l1 != NULL)    {        s = (List)malloc(sizeof(LNode));        s->data = l1->data;        l1 = l1->next;        s->next = NULL;        p->next = s;        p = p->next;    }    while(l2 != NULL)    {        s = (List)malloc(sizeof(LNode));        s->data = l2->data;        l2 = l2->next;        s->next = NULL;        p->next = s;        p = p->next;    }    return head->next;}*///两个有序链表合并函数优化List merge(List l1,List l2){    List head,p,s;    head = (List)malloc(sizeof(LNode));    p = head;    while(l1 != NULL || l2 != NULL)    {        s = (List)malloc(sizeof(LNode));        if(l1 != NULL && l1->data <= l2->data)        {            s ->data = l1->data;            l1 = l1->next;        }else{            s ->data = l2->data;            l2 = l2->next;        }        s->next = NULL;        p->next = s;        p = p->next;    }    return head->next;}//链表初始化函数List init_list(List head,int num){int i = 1;List p = head;while(i <= num){List s;s = (LNode*)malloc(sizeof(LNode));s->data = i * num;s->next = NULL;p->next = s;p = p->next;i++;}return head->next;}//链表输出函数void print_list(List head){List p;p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}printf("");}
    展开全文
  • 21.合并两个有序链表思路一 暴力 借用外部空间分别遍历两个链表,把数放到列表中,运用sort方法。再用尾插法,遍历列表,创建新有序链表。class Solution: def mergeTwoLists(self, l1:ListNode, l2:ListNode) -&...

    070e223c13f3d73b9da197dba7895903.png

    21.合并两个有序链表

    思路一 暴力 借用外部空间

    分别遍历两个链表,把数放到列表中,运用sort方法。再用尾插法,遍历列表,创建新的有序链表。

    class Solution:
        def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:
    
            sum = []
    
            def list2num(node):
                while node != None:
                    sum.append(node.val)
                    node = node.next
    
            list2num(l1)
            list2num(l2)
            sum.sort()
    
            dummy_node = ListNode(-1)
            start_node = dummy_node 
    
            for i in sum:
                new = ListNode(i)
                dummy_node.next = new
                dummy_node = new
            return start_node.next

    思路二 递归

    1. 时间复杂度 O(m+n) 每次递归调用都会去掉l1 或 l2 的头结点,至多会递归调用每个节点一次。

    因此,时间复杂度取决于合并后的链表长度。

    2. 空间复杂度 O(m+n) 至多调用函数 mergeTwoLists (m+n)次,每次调用需要消耗栈空间。

    因此,空间复杂度为O(m+n)

    class Solution:
        def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:
            if l1 == None:
                return l2
            elif l2 == None:
                return l1
            elif(l1.val < l2.val):
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2

    思路三 迭代

    先设立哨兵节点,为了好返回生成的链表

    用两个指针分别遍历两个链表,直到一方为空。

    遍历的过程中,比较两指针指向节点的大小,然后尾插法插入哨兵节点的next。

    直到一方为空,再把剩余不为空的链表插入。

    class Solution:
        def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:
    
            dummy_node = ListNode(-1)
            start_node = dummy_node
    
            while l1 and l2:
                if l1.val < l2.val:
                    dummy_node.next = l1
                    l1 = l1.next
                else:
                    dummy_node.next = l2
                    l2 = l2.next
                dummy_node = dummy_node.next
            return start_node.next
    展开全文
  • 两个有序链表的合并 题目要求: 本题要求实现一个函数,将两个链表表示的递增整数序列合并为一个非递减的整数序列。 函数接口定义: List Merge( List L1, List L2 ); 其中List结构定义如下: typedef struct ...

    两个有序链表的合并

    题目要求:

    本题要求实现一个函数,将两个链表表示的递增整数序列合并为一个非递减的整数序列。

    函数接口定义:
    List Merge( List L1, List L2 );
    

    其中List结构定义如下:

    typedef struct Node *PtrToNode;
    struct Node {
        ElementType Data; /* 存储结点数据 */
        PtrToNode   Next; /* 指向下一个结点的指针 */
    };
    typedef PtrToNode List; /* 定义单链表类型 */
    

    L1和L2是给定的带头结点的单链表,其结点存储的数据是递增有序的;函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点,返回归并后的带头结点的链表头指针。

    裁判测试程序样例:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElementType;
    typedef struct Node *PtrToNode;
    struct Node {
        ElementType Data;
        PtrToNode   Next;
    };
    typedef PtrToNode List;
    
    List Read(); /* 细节在此不表 */
    void Print( List L ); /* 细节在此不表;空链表将输出NULL */
    
    List Merge( List L1, List L2 );
    
    int main()
    {
        List L1, L2, L;
        L1 = Read();
        L2 = Read();
        L = Merge(L1, L2);
        Print(L);
        Print(L1);
        Print(L2);
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    
    输入样例:

    3
    1 3 5
    5
    2 4 6 8 10

    输出样例:

    1 2 3 4 5 6 8 10
    NULL
    NULL

    算法思想:

    将两个链表L1和L2从分别从第一个结点开始进行比较,较小的连在L上,然后继续让未遍历的L1,L2的结点进行分别比较,当某一个链表遍历结束后,进行判断,将未遍历完的链表全部链到L后面。

    注意:

    两个链表L1,L2带头结点。

    函数:
    /*
    【注意】
    1.两个链表L1,L2带头结点
    2.临时指针pL1和L1本质上并没有区别,都是实参L1的副本,使用pL1的目的是
    在函数中pL1作为移动的指针进行链接,而L1始终指向头结点(注意即使在函
    数中更改L1的指向,实参L1的指向也不会发生变化,不过函数最后的将L1置为
    空这一步会出问题)
    */ 
    /*
    【解题思路】
    将两个链表L1和L2分别从第一个结点开始进行比较,较小的连在L上,然后
    继续让未遍历的L1,L2的结点进行分别比较,当某一个链表遍历结束后,进行
    判断,将未遍历完的链表全部链到L后面 
    */  
    List Merge(List L1,List L2) {
    	List pL1,pL2,L0,L; // L0记录L的头结点,L为合并后的新链表
    	L = (List)malloc(sizeof(PtrToNode)); // L头结点 
    	L0 = L;
    	L -> Next = NULL;
    	pL1 = L1; pL2 = L2;
    	// 因为L1和L2是带头结点的链表,所以要让pL1和pL2分别指向第一个结点 
    	pL1 = pL1 -> Next; pL2 = pL2 -> Next; 
    	while(pL1 && pL2) {
    		if(pL1 -> Data <= pL2 -> Data) {
    			L -> Next = pL1;
    			L = L -> Next; 
    			pL1 = pL1 -> Next; 
    		}
    		else {
    			L -> Next = pL2;
    			L = L -> Next;
    			pL2 = pL2 -> Next;
    		}
    	}
    	//此时某一个链表已经遍历结束,下面进行判断,将未遍历的链表全部链到L后面 		
    	if(pL1) 
    		L -> Next = pL1;
    	else if(pL2)
    		L -> Next = pL2;
    	//根据题目要求,将L1和L2置为空 
    	L1 -> Next = NULL;
    	L2 -> Next = NULL;
    	return L0; //返回L的头结点 
    } 
    
    
    展开全文
  • 两个有序链表的合并要求给定两个有序链表,将两个链表合并为一个有序链表思路对于给定的链表l1和链表l2。定义一个链表l3来存储合并后的两个链表。定义两个指针,分别指向两个链表的头结点,在两个链表都不为空时,...
    7f877469abf8502260e35b1fec33d801.png

    两个有序链表的合并

    要求

    • 给定两个有序链表,将两个链表合并为一个有序链表

    思路

    • 对于给定的链表l1和链表l2。定义一个链表l3来存储合并后的两个链表。
    • 定义两个指针,分别指向两个链表的头结点,在两个链表都不为空时,比较两个链表结点的值的大小。若链表l1的节点大于l2的节点,则将l1的节点值赋值给l3。l1的指针指向下一个节点。反之,则则将l2的节点值赋值给l3。l2的指针指向下一个节点。
    • 两个链表出现一个为空时,判断哪个不为空,将该链表剩下的节点全部赋值给l3。

    图解

    42bc653a1efea862b18b159877134aaa.png

    两个有序链表的合并


    代码

    #include #include //构造结构体typedef struct list{int data;struct list *next;}*List,LNode;//函数声明List init_list(List head,int num);void print_list(List head);List merge(List l1,List l2);void main(){    List l,l1,l2;    l1 = (LNode*)malloc(sizeof(LNode));    l1 = init_list(l1,3);    l2 = (LNode*)malloc(sizeof(LNode));    l2 = init_list(l2,7);    l = merge(l1,l2);    print_list(l);}//两个有序链表合并函数/*List merge(List l1,List l2){    List head,p,s;    head = (List)malloc(sizeof(LNode));    p = head;    while(l1 != NULL && l2 != NULL)    {        s = (List)malloc(sizeof(LNode));        if(l1->data > l2->data)        {            s ->data = l2->data;            l2 = l2->next;        }else{            s ->data = l1->data;            l1 = l1->next;        }        s->next = NULL;        p->next = s;        p = p->next;    }    while(l1 != NULL)    {        s = (List)malloc(sizeof(LNode));        s->data = l1->data;        l1 = l1->next;        s->next = NULL;        p->next = s;        p = p->next;    }    while(l2 != NULL)    {        s = (List)malloc(sizeof(LNode));        s->data = l2->data;        l2 = l2->next;        s->next = NULL;        p->next = s;        p = p->next;    }    return head->next;}*///两个有序链表合并函数优化List merge(List l1,List l2){    List head,p,s;    head = (List)malloc(sizeof(LNode));    p = head;    while(l1 != NULL || l2 != NULL)    {        s = (List)malloc(sizeof(LNode));        if(l1 != NULL && l1->data <= l2->data)        {            s ->data = l1->data;            l1 = l1->next;        }else{            s ->data = l2->data;            l2 = l2->next;        }        s->next = NULL;        p->next = s;        p = p->next;    }    return head->next;}//链表初始化函数List init_list(List head,int num){int i = 1;List p = head;while(i <= num){List s;s = (LNode*)malloc(sizeof(LNode));s->data = i * num;s->next = NULL;p->next = s;p = p->next;i++;}return head->next;}//链表输出函数void print_list(List head){List p;p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}printf("");}
    展开全文
  • @2个有序链表的合并...两个有序链表的合并(递归方式) public class ListedMerge { //定义聊表节点 public static class ListNode{ int value; ListNode next; public ListNode(int value) { th...
  • 新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4, 1->3->4输出:1->1->2->3->4->4(1)思路:递归(2)代码#include using namespace std;struct ListNode{ int val; ...
  • //两个有序链表的合并 递归实现 #include&lt;iostream&gt; using namespace std; struct NODE { int data; NODE *next; }; NODE *Listmerge(NODE *L1,NODE *L2) { if(L1==NULL) return 0; if(L2==NULL...
  • 算法:两个有序链表的合并

    千次阅读 2014-04-18 21:10:34
    两个有序链表的合并操作
  • 数据结构实现两个有序链表的合并(c语言)

    万次阅读 多人点赞 2019-03-28 21:16:55
    数据结构实现两个有序链表的合并(c语言) 现有两个有序单链表,通过代码实现将两个单链表合并为一个有序的新表,要求使用旧表的空间,不能新分配内存 #include <stdio.h> #include <stdlib.h> typedef ...
  • 两个有序链表的合并 这个题是对链表操作的一个基本熟悉,适合新手小白做,思路是比较清晰的 函数接口定义: List Merge( List L1, List L2 ); 其中List结构定义如下: typedef struct Node *PtrToNode; struct Node...
  • 根据链表数据结构的知识,进行初步练习,从单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串四个题目着手,分别进行代码实现。 首先定义单链表类: # 结点类 class Node(object): def _...
  • 已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并非降序链表S3。输入格式:输入分两行,分别在每行给出由若干个正整数构成非降序序列,用−1表示序列结尾(−1不属于这个序列)。数字用空格间隔。...
  • 两个有序链表的合并与交集

    千次阅读 2017-12-05 22:49:24
    两个有序链表序列的合并 已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的并集新非降序链表S3。 输入格式: 输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−表示序列的结尾(−不属于这...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 思路 建立一个新的头节点,两...
  • 两个有序链表的合并(JAVA)

    千次阅读 2019-03-14 14:34:29
    有序链表合并思路 原链表m和n都是有序的,比如都是正序排列(从小到大) 两个链表同时从头开始向后移动 移动前先比较节点大小,更小的存入新链表的链尾(此为中间步骤) 直到有一个链表移动结束,再将另一个链表的...
  • //实现一个函数,输入两个链表(递增),合并为一个链表,依然保持有序。 package com.offer.test.listnodecomb; class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; ...

空空如也

空空如也

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

两个有序链表的合并