精华内容
下载资源
问答
  • 主要介绍了JS实现的合并两个有序链表算法,结合实例形式分析了JavaScript链表的定义、节点插入、删除、查找等相关算法实现技巧,需要的朋友可以参考下
  • 主要介绍了Python实现合并两个有序链表的方法,涉及Python操作链表节点的遍历、判断、添加等相关操作技巧,需要的朋友可以参考下
  • 主要介绍了c++ 如何合并两个有序链表,帮助大家更好的理解和学习C++,感兴趣的朋友可以了解下
  • 合并两个有序链表

    2020-02-08 13:43:41
    1. 合并两个有序链表实现 使用递归方式 public static LinkedNode mergeWithRecursive(LinkedNode head1, LinkedNode head2){ if(head1 == null && head2 == null){ return null; } if(head1 == ...
    1. 合并两个有序链表实现

    使用递归方式

    public static LinkedNode mergeWithRecursive(LinkedNode head1, LinkedNode head2){
    	if(head1 == null && head2 == null){
    		return null;
    	}
    	
    	if(head1 == null){
    		return head2;
    	}
    	
    	if(head2 == null){
    		return head1;
    	}
    	
    	// head1 & head2 not null
    	LinkedNode head = null;
    	if(head1.item <= head2.item){
    		head = head1;
    		head.next = mergeWithRecursive(head1.next, head2);
    	}else{
    		head = head2;
    		head.next = mergeWithRecursive(head1, head2.next);
    	}
    	return head;
    }
    

    使用非递归方式

    public static LinkedNode mergeSortedLinked(LinkedNode head1, LinkedNode head2){
    	if (head1 == null || head2 == null){
    		return head1 == null? head2:head1;
    	}
    	
    	// 第一个元素最小值的链表
    	LinkedNode min_cur = head1.item <= head2.item?head1:head2;
    	// 第一元素较大的链表
    	LinkedNode max_cur =  min_cur == head1?head2:head1;
    	
    	// 以min_cur为基准,将max_cur合并到min_cur
    	LinkedNode min_pre = null;	// min_cur的上一个节点
    	LinkedNode max_next = null;	// max_cur的下一个节点
    	
    	// 目标节点
    	LinkedNode head = min_cur;
    	while(min_cur != null && max_cur != null){
    		if(min_cur.item <= max_cur.item){
    			// min的节点小于max节点,继续循环遍历
    			min_pre = min_cur;
    			min_cur = min_cur.next;
    		}else{
    			// 因为以min为基准,因此第一次循环的时候会在上面的if获取到min_pre的值
    			min_pre.next = max_cur;
    			// 保存max的next节点
    			max_next = max_cur.next;
    			// 连接到min的节点上,断开当前的max节点,将其的next指向min当前的节点
    			max_cur.next = min_cur;
    			// min_cur的上一个节点移动到当前的max节点
    			min_pre = max_cur;
    			// 	循环遍历下一个max的节点
    			max_cur = next;
    		}
    	}
    	// 最后需要判断下节点,将末尾的所有节点连接起来
    	prev.next = min_cur == null?max_cur:min_cur;
    	return head;
    }
    
    2.合并两个链表非递归图解说明

    初始化状态

    • 代码如下
    // 确定min和max节点
    LinkedNode min_cur = head1.item <= head2.item?head1:head2;
    LinkedNode max_cur =  min_cur == head1?head2:head1;
    
    • 其初始化图解如下
      在这里插入图片描述

    第一次循环遍历

    • 此时执行的代码
    if(min_cur.item <= max_cur.item){
    	// min的节点小于max节点,继续循环遍历
    	min_pre = min_cur;
    	min_cur = min_cur.next;
    }else{
    	// ...
    }
    
    • 图解如下
      在这里插入图片描述
    • 此时min_pre指向min链表中值为1的节点
    • min_cur,即当前的指针指向min链表中值为2的节点

    循环执行到else的语句分析

    • 执行代码
    // 因为以min为基准,因此第一次循环的时候会在上面的if获取到min_pre的值
    min_pre.next = max_cur;			// 1
    // 保存max的next节点
    max_next = max_cur.next;		// 2
    // 连接到min的节点上,断开当前的max节点,将其的next指向min当前的节点
    max_cur.next = min_cur;			// 3
    // min_cur的上一个节点移动到当前的min节点
    min_pre = max_cur;				// 4
    // 	循环遍历下一个max的节点
    max_cur = next;					// 5
    
    • 执行代码前的图解
      在这里插入图片描述
    • 执行代码过程图解
      在这里插入图片描述
    • min_pre此时的指针为min链表中值为2的节点
    • 执行1的代码之后,min_prev的next指针指向max当前的节点,也就是值为2的max链表的节点
    • 执行2的代码之后,max_next的指针指向max当前节点的下一个节点,也就是值为4的节点
    • 执行3的代码之后,max_cur的next指针指向min当前的节点,也就是min链表中值为5的节点
    • 执行4的代码之后,min_prev的指针指向当前max的节点,也就是值为2的max链表的节点
    • 执行5的代码之后,max_cur当前指针指向max值为4的节点
    • 执行代码后的图解
      在这里插入图片描述
    • 根据上述代码以及图解的节点值再执行else代码
      在这里插入图片描述
    • 此时的min_prev的指针指向max链表值为2的节点
    • 执行1代码之后,min_prev的next指针指向max_cur节点,也就是值为4的max节点
    • 执行2代码之后,max_next的指针指向值为6的max节点
    • 执行3代码之后,max_cur当前的next指针指向当前min_cur的节点,也就是值为5的min节点
    • 执行4代码之后,min_prev的指针指向当前max的节点,也就是值为4的max节点
    • 执行5代码之后,max指针指向max_next的节点,也就是当前值为6的max节点
      在这里插入图片描述
    • 此时再次循环,min_cur.item < max_cur.item,执行流程如下
    prev = min_cur; //1
    min_cur = min_cur.next; //2
    

    执行过程
    在这里插入图片描述
    执行结果
    在这里插入图片描述
    接下来动作重复上述流程,可以看到prev 始终跟在min_cur之后,在经历整个循环之后,说明至少有一个链表已经遍历完成,最后只需要将prev的next节点与剩下的节点连接即可,最后max所有节点都将有序地合并到min中

    • 小结
      • 使用的时间复杂度为O(n),空间复杂度为O(1)
    展开全文
  • C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
  • 数据结构-链表-合并两个有序链表(递归详细分析实现) 题目描述 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 /*数据结构*/ ListNode { int val; ListNode *...

    合并两个有序链表(递归)

    题目描述

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

    示例

    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4
    

    先看一下代码

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            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 ;  
            }
            
        }
    }
    

    分析

    这个算法,来自大名鼎鼎的归并排序,你一下子看不懂很正常,你可以这么来理解,两个链表之间通过比大小玩连连看,在链表一或链表二最后的结点,开始往回走,把之前比较的结点按序连成一条线,最终返回的就是一个合并好的链表

    如果还是理解不了,你可以以一个极端的例子,去代入这段代码,帮助你理解

    123)
    (456

    性能分析

    时空复杂度皆为O(m+n)两个链表的结点总和,在这道题中,不一定每个结点都会被访问到,如上面举例的极端情况,所以实际时空复杂度应该是小于O(m+n)
    ==========update by 2020 4/16 ========

    可运行代码

    #include "stdio.h"    
    #include "string.h"
    #include "ctype.h"      
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    #define MAXSIZE 20 /* 存储空间初始分配量 */
    
    typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */
    
    
    Status visit(ElemType c)
    {
    	printf("%d ", c);
    	return OK;
    }
    
    
    
    typedef struct ListNode
    {
    	ElemType val;
    	struct ListNode *next;
    }ListNode;
    typedef struct ListNode *LinkList; /* 定义LinkList */
    
    /* 初始化顺序线性表 */
    Status InitList(LinkList *L)
    {
    	*L = (LinkList)malloc(sizeof(ListNode)); /* 产生头结点,并使L指向此头结点 */
    	if (!(*L)) /* 存储分配失败 */
    		return ERROR;
    	(*L)->val = NULL;
    	(*L)->next = NULL; /* 指针域为空 */
    
    	return OK;
    }
    
    
    
    /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */
    /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */
    Status ListInsert(LinkList *L, int i, ElemType e)
    {
    	int j;
    	LinkList p, s;
    	p = *L;
    	j = 1;
    	while (p && j < i)     /* 寻找第i个结点 */
    	{
    		p = p->next;
    		++j;
    	}
    	if (!p || j > i)
    		return ERROR;   /* 第i个元素不存在 */
    	s = (LinkList)malloc(sizeof(ListNode));  /*  生成新结点(C语言标准函数) */
    	s->val = e;
    	s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
    	p->next = s;          /* 将s赋值给p的后继 */
    	return OK;
    }
    
    
    
    /* 初始条件:顺序线性表L已存在 */
    /* 操作结果:依次对L的每个数据元素输出 */
    Status ListTraverse(LinkList L)
    {
    	LinkList p = L->next;
    	while (p)
    	{
    		visit(p->val);
    		p = p->next;
    	}
    	printf("\n");
    	return OK;
    }
    
    
    
    
    
    LinkList mergeTwoLists(LinkList l1, LinkList l2) {
    
    
    	/*递归出口*/
    	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;
    	}
    
    }
    
    
    
    int main()
    {
    	LinkList L;
    	LinkList L2;
    	LinkList L3; 
    
    	ElemType e;
    	Status i;
    	int j, k;
    	/*1.初始化单链表*/
    	i = InitList(&L);
    
    	/*2.依次采用尾插法插入abcde元素*/
    
    	ListInsert(&L, 1, 1);
    	ListInsert(&L, 2, 2);
    	ListInsert(&L, 3, 4);
    
    	i = InitList(&L2);
    
    	ListInsert(&L2, 1, 1);
    	ListInsert(&L2, 2, 3);
    	ListInsert(&L2, 3, 4);
    
    
    
    	L3 = mergeTwoLists(L, L2); 
    
    	/*11.输出单链表*/
    	printf("输出单链表\n");
    	ListTraverse(L3);
    
    
    	system("pause");
    	return 0;
    
    
    
    }
    
    展开全文
  • 合并两个有序链表(python)

    千次阅读 2020-05-13 20:29:48
    文章目录题目描述题目分析代码 ...将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3

    题目描述

    leetcode题目链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/

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

    示例:
    
    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4
    

    题目分析

    1. 方法一:递归
      我们递归定义两个链表里的 merge 操作,先不考虑边界:
      { l i s t 1 [ 0 ] + m e r g e ( l i s t 1 [ 1 ] , l i s t 2 [ 0 ] ) l i s t 1 [ 0 ] < l i s t 2 [ 0 ] l i s t 2 [ 0 ] + m e r g e ( l i s t 1 [ 0 ] , l i s t 2 [ 1 ] ) o t h e r v i s e \left\{ \begin{aligned} &list1[0] + merge(list1[1], list2[0]) & list1[0]<list2[0]\\ &list2[0] + merge(list1[0], list2[1]) & othervise \end{aligned} \right. {list1[0]+merge(list1[1],list2[0])list2[0]+merge(list1[0],list2[1])list1[0]<list2[0]othervise
      也就是说,两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
      考虑边界:若l1,或者l2其中一方为空,返回另一方。若开始皆为空,那返回另一方也为空,也满足条件。

    2. 方法二:迭代
      迭代初始:建立头指针FNode,和一个前向指针pre初始指向FNode
      迭代开始:将pre.next指向两链表中值小的节点上,pre前移。
      迭代结束:定有一方链表指针为None,将pre.next指向将另一方当前节点上。返回FNode.next
      特殊情况:一开始两链表均为None,返回值也是None,满足条件。

    代码

    /*
    方法1: 递归
    */
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            if not l1:
                return l2
    
            if not l2:
                return l1
    
            if l1.val < l2.val:
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l2.next, l1)
                return l2
    
    /*
    方法二:迭代
    */
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            FNode = ListNode(-1)
    
            pre = FNode
    
            while l1 and l2:
                if l1.val < l2.val:
                    pre.next = l1
                    l1 = l1.next
                else:
                    pre.next = l2
                    l2 = l2.next
                pre = pre.next
    
            pre.next = l1 if l1 else l2
    
            return FNode.next
    
    展开全文
  • 合并两个有序链表 LeetCode21.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 解法...

    合并两个有序链表

    LeetCode21.合并两个有序链表

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

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

    解法一:迭代

    合并前:
    在这里插入图片描述

    合并后:

    在这里插入图片描述

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            //不排除其中有一条链是空链的可能,这时返回另一条
            if (nullptr == l1)
                return l2;
            if (nullptr == l2)
                return l1;
            ListNode head(-1);
            ListNode* phead = &head;
            while (nullptr != l1 && nullptr != l2) {
                if (l1->val > l2->val) {
                    //phead->next取较小者
                    phead->next = l2;
                    l2 = l2->next;
                }
                else {
                    phead->next = l1;
                    l1 = l1->next;
                }
                phead = phead->next;
            }
            //接上还未排完的
            phead->next = l1 == nullptr ? l2 : l1;
            return head.next;
        }
    };
    

    解法二:递归

    每次递归都使当前较小值,指向下一个较小值,递归返回时,返回该最小值的节点。

    在这里插入图片描述

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if (nullptr == l1)
                return l2;
            if (nullptr == l2)
                return l1;
            if (l1->val > l2->val) {
                //l2小,所以l1和l2->next比较,填的是l1和l2->next          
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
    };
    
    展开全文
  • 合并两个有序链表 图解说明

    千次阅读 多人点赞 2020-11-29 12:09:29
    合并两个有序链表 题目描述 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->...
  • 合并两个有序链表(java)

    千次阅读 2019-07-29 17:55:43
    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 想法☁: 1.题目告诉两个链表,那你首先应想到,如果给你的两个链表的其中一个是空的,则返回另外一个链表节点头...
  • 什么是合并两个有序链表 假设有两条链表,这两条链表分别都是升序排列的,如下图所示: 现在要求将二者合并成一条链表,并且该链表也是升序排列的,合并后的链表如下图所示: 思路 如果对归并排序有所了解,那么这...
  • java实现----合并两个有序链表

    千次阅读 2019-05-06 21:52:29
    合并两个有序链表,原来两个链表是有序的,合并完整体也要保证有序 思路: 同时遍历两个链表的各自结点 进行值的比较,哪个值小就放入到新的链表中 放置的方式是尾插,当一个链表中的所有结点都被取走之后,直接将...
  • 作者:CYL ...思路一、最傻逼的方法是遍历一遍然后把值存在列表里面 然后 对列表排序 再构建新的有序链表 如果给定两个无序链表 那这种方法是切实有效的 但是当给定两个有序链表显然不太合适 思路二、两个
  • 合并两个有序链表一、题目二、代码实现 【LeetCode】21. 合并两个有序链表 一、题目 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4,...
  • 两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 2 输入输出 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 3 解答 1)...
  • 两个有序链表合并

    2019-03-14 11:16:17
    两个有序链表合并成一个链表合并后的链表仍然是有序的,依次输出合并后的链表的元素值,并求出第奇数位置元素之和
  • var mergeTwoLists = function(l1, l2) { if(!l1){ return l2; } if(!l2){ return l1; } if(l1.val<l2.val){ l1.next=mergeTwoLists(l1.next,l2); return l1; }else{ l2.next=mergeTwoLists(l1,l2....
  • 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 C 思想:...
  • 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 解法一(非...
  • 这次来写一下 LeetCode 的第 21 题,合并两个有序链表。 题目描述 题目直接从 LeetCode 上截图过来,题目如下: 上面的题就是 合并两个有序链表 题目的截图,同时 LeetCode 会根据选择的语言给出了一个...
  • LeetCode 图解 | 21.合并两个有序链表

    千次阅读 2020-01-17 12:15:00
    点击上方蓝字设为星标下面开始今天的学习~今天分享的题目来源于 LeetCode 上第 21 号问题:合并两个有序链表。题目描述将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接...
  • 合并两个有序链表『java实现』

    千次阅读 2020-08-11 18:04:22
    创建一有带头结点的新链表,比较L1 与L2的结点值,若L1当前的结点值小于或等于L2当前的结点值,把小的先放进新链表中,然后再比较L1的下一结点,直至为空。也就是如下的迭代思想了。 个人在思想出现误区: 创建...
  • 1. 合并两个有序链表 描述: 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路: (1)先定义一个傀儡指针ListNode perHead = new ListNode(-1),再定义...
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/ 著作权归领扣网络...
  • 合并两个有序链表(Java实现) 题目:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->...
  • 合并两个有序链表(C语言)

    千次阅读 2019-04-26 18:54:12
    两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 解决思路 1.排列顺序为由小到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,050
精华内容 18,420
关键字:

合并两个有序链表