精华内容
下载资源
问答
  • LeetCode 合并两个有序链表递归实现) 乍看上去,这段代码不是很容易理解,但是代码很经典。 记住一句话,递归是基于功能,对于后面已经排好序链表,只需要排好前面节点就好了。 /** * Definition for ...

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

    乍看上去,这段代码不是很容易理解,但是代码很经典。
    记住一句话,递归是基于功能的,对于后面已经排好序的链表,只需要排好前面的节点就好了。

    /**
     * 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;
     		//需要返回的头指针
            ListNode head = null;
            if (l1.val <= l2.val){
            //对于对象,这地方是引用传值。
                head = l1;
                head.next = mergeTwoLists(l1.next, l2);
            } else {
                head = l2;
                head.next = mergeTwoLists(l1, l2.next);
            }
     
            return head;
        }
    }
    
    

    算法,有看不懂的地方,画个图,举个例子就能理解了。

    展开全文
  • 先看代码的实现:#include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; //链表存储结构 typedef struct Node { int number; struct Node * next; }Node; typedef struct Node * LinkList; void ...

          先看代码的实现:

    #include<stdio.h>
    #include<stdlib.h>
    //链表存储结构
    typedef struct Node
    {
    	int number;
    	struct Node * next;
    }Node;
    typedef struct Node * LinkList;
    
    void createListHead(LinkList * pHead, int option) //形参pHead为指向指针的指针 
    {
    	LinkList p, r;
    	int i;
    	*pHead = (LinkList)malloc(sizeof(Node));   //头结点,不存数据 
    	r = *pHead;
    	if (option == 1)  //生成奇数递增链表
    	{
    		for (i = 1; i < 11; i += 2)
    	    {
    			p = (LinkList)malloc(sizeof(Node));
    			p->number = i;
    			r->next = p;
    			r = p;
    	    }	
    	} 
    	else if (option == 2)   //生成偶数递增链表 
    	{
    		for (i = 2; i < 10; i += 2)
    	    {
    			p = (LinkList)malloc(sizeof(Node));
    			p->number = i;
    			r->next = p;
    			r = p;
    	    }		
    	} 
    
    	r->next = NULL;
    }    
    
    void displayElem(LinkList pHead)
    {
    	while (pHead)
    	{
    		printf("%d\t", pHead->number);
    		pHead = pHead->next;	
    	}
    	printf("\n");
    }
    
    LinkList mergedList(LinkList pHead1, LinkList pHead2)
    {
    	LinkList pHead = NULL;
    	if (pHead1 == NULL)
    	{
    		return pHead2;	
    	}
    	else if (pHead2 == NULL)
    	{
    		return pHead1;	
    	}
    	
    	if (pHead1->number < pHead2->number)
    	{
    		pHead = pHead1;
    		pHead->next = mergedList(pHead1->next, pHead2);	
    	}
    	else
    	{
    		pHead = pHead2;
    		pHead->next = mergedList(pHead1, pHead2->next);	
    	}
    	return pHead;
    	
    }
    int main()
    {
    	LinkList pHead1 = NULL;
    	LinkList pHead2 = NULL;
    	LinkList pHead = NULL;
    	createListHead(&pHead1, 1);   /*传入指针本身的地址,这里读者得好好想想,为什么这样 
    	                               *相当于是传入pHead1这个指针本身的地址,然后在
    								   *createListHead函数中操纵这个指针pHead1,让它有指向
    								   */ 
    	createListHead(&pHead2, 2); 
    	displayElem(pHead1->next);
    	displayElem(pHead2->next);    //pHead1和pHead2就是两个排好序的链表 
    	
    	//下面要将这两个排好序的链表组合成一个有序的递增链表 
    	pHead = mergedList(pHead1->next, pHead2->next);
    	displayElem(pHead);
    	return 0;
    }
    程序运行显示结果:


         两个有序递增的链表pHead1和pHead2,如果pHead1的第一个结点的值大于pHead2的第一个结点的值,就将pHead1的头结点赋值给pHead。然后进行下一次的比较,反之就是pHead2赋给pHead。如图:

        
       这就是一个递归的过程,当到链表的最后一个结点的位置后,递归结束,依次返回各个递归函数的结点,最后组合成一个链表——合并之后的有序链表。

        关于链表的知识,亲可以去查看《大话数据结构》哦!

    后边在一个公司面试Java职位的时候,当时让我手写这个算法,用的是非递归的方式,看Java代码: 

    public class MergeSortedLinkedList {
        public class Node {
            private int number;
            private Node next;
            Node(int number, Node next) {
                this.number = number;
                this.next = next;
            }
        }
    
        /**
         * 返回头节点
         * @param isOdd
         * @return
         */
        public Node createSortedLinkedList(boolean isOdd) {
            Node p, head;
            // 头结点
            p = head = new Node(0, null);
            if (isOdd) {
                // 创建奇数有序链表
                for (int i = 1; i < 20; i += 2) {
                    Node node = new Node(i, null);
                    p.next = node;
                    p = node;
                }
            } else {
                // 创建偶数有序链表
                for (int i = 2; i < 20; i += 2) {
                    Node node = new Node(i, null);
                    p.next = node;
                    p = node;
                }
            }
            return head;
        }
    
        public Node mergeTwoSortedLinkedList(Node head1, Node head2) {
            // 注意参数判断,这个面试官也很看重 
            if (null == head1) {
                return head2;
            }
            if (null == head2) {
                return head1;
            }
    
            // 给新merge的头结点设值
            Node p, head;
            if (head1.number < head2.number) {
                head = head1;
                head1 = head1.next;
            } else {
                head = head2;
                head2 = head2.next;
            }
            p = head;
    
            while (null != head1 && null != head2) {
                if (head1.number < head2.number) {
                    p.next = head1;
                    // p指针向下移动到新结点
                    p = head1;
                    head1 = head1.next;
                } else {
                    p.next = head2;
                    p = head2;
                    head2 = head2.next;
                }
            }
            // 对剩余结点的处理 
            if (null != head1) {
                p.next = head1;
            }
            if (null != head2) {
                p.next = head2;
            }
            return head;
        }
    
        public void display(Node node) {
            while (null != node) {
                System.out.print(node.number + " ");
                node = node.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            MergeSortedLinkedList sortedLinkedList = new MergeSortedLinkedList();
            Node head1 = sortedLinkedList.createSortedLinkedList(true);
            Node head2 = sortedLinkedList.createSortedLinkedList(false);
            System.out.print("Linked list one: ");
            sortedLinkedList.display(head1.next);
            System.out.print("Linked list two: ");
            sortedLinkedList.display(head2.next);
            System.out.print("Merged linked List: ");
            sortedLinkedList.display(sortedLinkedList.mergeTwoSortedLinkedList(head1.next, head2.next));
        }
    }


    展开全文
  • 递归实现 ListNode* mergeList(ListNode* head1, ListNode* head2) { if(head1 == nullptr) return head2; else if(head2 == nullptr) return head1; ListNode* res = nullptr; if(head1 -&gt; val &...

    递归实现

    ListNode* mergeList(ListNode* head1, ListNode* head2)
    {
    	if(head1 == nullptr)
    		return head2;
    	else if(head2 == nullptr)
    		return head1;
    	
    	ListNode* res = nullptr;
    	if(head1 -> val < head2 -> val) {
    		res = head1;
    		res -> next = mergeList(head1 -> next, head2);
    	} else {
    		res = head2;
    		res -> next = mergeList(head1, head2 -> next);
    	}
    	
    	return res;
    }
    

    非递归实现

    ListNode* mergeList(ListNode* head1, ListNode* head2)
    {
    	ListNode* dummy = new ListNode(-1);
    	ListNode* last = dummy;
    	while(head1 && head2) {
    		if(head1 -> val < head2 -> val) {
    			last -> next = head1;
    			last = last -> next;
    			head1 = head1 -> next;
    		} else {
    			last -> next= head2;
    			last = last -> next;
    			head2 = head2 -> next;
    		}
    	}
    	if(head1)
    		last -> next = head1;
    	else if(head2)
    		last -> next = head2;
    	
    	ListNode* res = dummy -> next;
    	delete dummy;
    	return res;
    }
    
    展开全文
  • 数据结构-链表-合并两个有序链表递归详细分析实现) 题目描述 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 /*数据结构*/ 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;
    
    
    
    }
    
    展开全文
  • 递归和非递归的方法合并两个有序链表
  • 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 /** * ...
  • package DataStructure.linkedlist; /** * Created on 2019/9/25 15:50 * 合并两个有序的单链表 * * @author Haiyang He * @version 1.0 */ public class ... * 以递归的方式合并两个有序的单链表 ...
  • 新链表是通过拼接给定的两个链表的所有节点组成的。 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 利用了递归的思想: 首先将两个链表传入,之后开始按照元素顺序进行对比,返回较小值后继续进行递归直到...
  • 新链表是通过拼接给定的两个链表的所有节点组成的。 示例 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 输入:l1 = [], l2 = [] 输出:[] 输入:l1 = [], l2 = [0] 输出:[0] 解题思路 // A code block ...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 思路 标签:链表、...
  • 实现思路请参考官方题解。 /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function (l1, l2) { // 如果l1为null,无需继续遍历。 // 只需要把l2剩余节点...
  • https://leetcode-cn.com/problems/merge-two-sorted-lists/description/合并两有序链表,形成一条新的有序链表:用递归实现1.如果其中一条链表为空,那么只需要接上(返回)另一条链表即可2.两条链表都不为空话...
  • 合并两个有序链表 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 /** * ...
  • 题目: 将两个有序链表合并为一个新的有序链表并返回。...4看到这个题,让我想起上次写的博客,合并两个有序的数组。这个题,是链表的合并,这就比较好移动,可以用递归实现链表的拼接所以,代...
  • 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4,1->3->4 输出:1->1->2->3->4->4 解题...
  • 递归实现与非递归实现 /** * @Description: 链表的遍历 * * @Date: * @Author: fuGuoWen * @Return ... * @Description: 合并两个有序的链表 非递归实现 * 时间复杂度O(m+n) 空间复杂度O(1) * @Da
  • //两个有序链表的合并 递归实现 #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...
  • package com.wyl.linklist; /** * 合并两个链表 * @author wyl */ public class MergeLinkList { /** * 内部类,链表节点结构 * @author wyl * */ public static class Node{...
  • 合并两个有序链表 问题描述: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->...
  • 新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ...
  • 新链表是通过拼接给定的两个链表的所有节点组成的。 代码实现(非递归) class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* preHead=new ListNode(-1); ListNode* ...
  • 递归实现合并两个有序链表。 本篇文章介绍另一种方法来实现。 其它函数不变,只需修改合并链表的函数。 ListNode* MergeTList1(ListNode* l1,ListNode* l2) { //判断两个链表是否为空,如果其中一个为空,那么合并...
  • .合并两个有序链表

    2020-12-26 20:37:19
    21.合并两个有序链表 思想 递归: 终止条件:链表为空表示合并完成 递归体:如果l1头结点小就使l1指向合并后链表,反之亦然. 实现: 总结:递归时把递归体看做无序集合,通过一步步积累到最后一步出现具体数值. ...
  • 面试题:合并两个有序链表,合并之后需要变为有序 对于此题,我想到有两种解法:递归和非递归 递归实现: //递归 Node *MergeList(Node *pHead1, Node*pHead2) { if (pHead1 == NULL) return pHead2; ...
  • 合并两个有序链表

    2019-04-18 21:24:11
    leetcode 21题,合并两个有序链表 java通过递归实现 /** * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 * 输入:1->2->4, 1->3->4 * 输出:1-&...
  • LeetCode-合并两个有序链表(java实现)

    万次阅读 多人点赞 2018-08-03 11:19:21
    题目如下 ...提交时候就没有用递归实现,运行结果可想而知:23ms。看了第一名用时是5ms,而且代码简洁优美,不得不佩服 /** *Definition for singly-linked list */ class ListNode{ int val; L...
  • 1.题目要求 这是一道求职面试时经常... 输入:两个有序的单链表head1与head2;  输出:合并有序单链表mergeHead;  算法描述:  (1)如果head1或head2为空链表,则直接返回另外一个链表;  (2)选择h

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 252
精华内容 100
关键字:

合并两个有序链表的递归实现