本文共 3065 字,大约阅读时间需要 10 分钟。
【JZ16】输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
知识点:单链表,递归 难度:☆算法步骤:
1、定义一个新的链表头结点head
、两个链表的指针结点index1
和index2
、head
的指针结点temp
; 2、判断index1
和index2
的大小,如果index1
小,则temp.next = index1
,然后temp = temp.next
,index1 = index.next
; 3、如果index1=null
,说明list1
已经遍历完了,list2
的剩余元素直接拼接到temp
后面即可,即temp.next = index2
。 递归法的思路就是:
1、函数的功能是什么? 2、函数的结束条件是什么? 3、函数一定在逼近结束条件,如何逼近? 根据本题我们来回答上面三个问题: 1、函数的功能是:合并两个单链表,返回两个单链表头结点值小的那个节点; 2、其中一个链表为空,则直接返回另一个链表; 3、如果list1
的所指节点值小于等于list2
所指的结点值,那么list.next
节点和list2
节点继续递归。 package pers.klb.jzoffer.medium;/** * @program: JzOffer2021 * @description: 合并两个排序的链表(迭代法) * @author: Meumax * @create: 2020-07-11 10:21 **/public class MergeList { /** * 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 * * @param list1 * @param list2 * @return */ public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } else if (list2 == null) { return list1; } ListNode index1 = list1; ListNode index2 = list2; ListNode head = new ListNode(0); // 头结点 ListNode temp = head; while (true) { if (index1.val <= index2.val) { temp.next = index1; index1 = index1.next; temp = temp.next; // 如果list1遍历完了,剩余的list2直接拼接在后面 if (index1 == null) { temp.next = index2; break; } } else { temp.next = index2; index2 = index2.next; temp = temp.next; // 如果list2遍历完了,剩余的list1直接拼接在后面 if (index2==null){ temp.next = index1; break; } } } return head.next; }}class ListNode { public int val; public ListNode next = null; public ListNode(int val) { this.val = val; }}
时间复杂度:O(m+n),m,n分别为两个单链表的长度
空间复杂度:O(1)package pers.klb.jzoffer.medium;/** * @program: JzOffer2021 * @description: 合并两个排序的链表(递归法) * @author: Meumax * @create: 2020-07-11 10:21 **/public class MergeList { /** * 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 * * @param list1 * @param list2 * @return */ public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } else if (list2 == null) { return list1; } else { if (list1.val <= list2.val) { list1.next = Merge(list1.next, list2); return list1; } else { list2.next = Merge(list1, list2.next); return list2; } } }}class ListNode { public int val; public ListNode next = null; public ListNode(int val) { this.val = val; }}
时间复杂度:O(m+n)
空间复杂度:O(m+n),每一次递归,递归栈都会保存一个变量,最差情况会保存(m+n)个变量本题难度偏低,无论是迭代还是递归,都是比较容易想到的,但貌似递归比迭代还难那么一点点。
转载地址:http://ubok.baihongyu.com/