LeetCode21 合并两个有序链表
news/发布时间
2024/5/14 8:52:24
- 题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 示例
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:输入:l1 = [], l2 = []
输出:[]
示例 3:输入:l1 = [], l2 = [0]
输出:[0]
- 解题思路
- 递归。链表list1、list2,比较两个链表的头节点,若list1头结点的值小于list2头结点的值,则以list1为头结点,再对list1剩余节点及list2两个链表合并,将合并结果作为list头结点的next。知道list1和list2都空为止。
- 循环(额外空间)。使用两个指针分别遍历两个链表,比较两个量表list1、list2的每一个节点的大小。使用额外空间作为结果链表。将较小的节点添加到新链表。
- 循环(链表本身)。与使用循环方式类似,通过一个记录前节点的指针pre进行构造链表。
- 两个链表list1、list2,两个指针l1、l2分别指向list1、list2。
- 比较l1、l2两个节点大小。
- 若l1小,则pre.next为l1节点。此时l1节点已经进入结果链表,则l1指针向后移动。指向l1.next。
- 若l2小,则pre.next为l2节点。此时l2节点已经进入结果链表,则l1指针向后移动。指向l2.next。
- 比较后,此时结果链表当前节点的pre指针需要向后移动。当前节点为l1或l2.
- 循环此过程,知道l1或l2链表为空。
- 此时,只剩一个链表没有合并到结果链表中。将剩余链表合并到结果中。
- 代码(Java)
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}
// 方法一class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}if (list1.val < list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}}
}
// 方法二
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}ListNode p1 = list1;ListNode p2 = list2;ListNode root = null;ListNode temp = null;while (p1 != null && p2 != null) {if (p1.val <= p2.val) {if (root == null) {root = temp = new ListNode(p1.val, null);} else {temp.next = new ListNode(p1.val, null);temp = temp.next;}p1 = p1.next;} else {if (root == null) {root = temp = new ListNode(p2.val, null);} else {temp.next = new ListNode(p2.val, null);temp = temp.next;}p2 = p2.next;}}if (p1 != null) {temp.next = p1;}if (p2 != null) {temp.next = p2;}return root;}
}
// 方法三class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}ListNode head = new ListNode(-1);ListNode pre = head;ListNode l1 = list1;ListNode l2 = list2;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {pre.next = l1;l1 = l1.next;} else {pre.next = l2;l2 = l2.next;}pre = pre.next;}if (l1 != null) {pre.next = l1;}if (l2 != null) {pre.next = l2;}return head.next;}
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.bcls.cn/CabH/4982.shtml
如若内容造成侵权/违法违规/事实不符,请联系编程老四网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!