[Leetcode]21. 合并两个有序链表
2022/4/29 23:15:14
本文主要是介绍[Leetcode]21. 合并两个有序链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:21. 合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com)
思路:
有两个有序链表l1和l2,这里的l1和l2是分别指向这两个有序链表的,按着顺序迭代两个链表。
无虚拟节点的情况:
确定合并链表的头节点指针head这里要对两个链表的情况进行划分,有四种情况:
1. 若l1==null && l2 == null,则合并的链表自然为空,head=null
2. 若l1 == null && l2 != null,则合并的链表即为l2,返回l2即可,head=l2
3. 若l1 != null && l2 == null,则合并的链表即为l1,返回l1即可,head=l1
4.若l1 != null && l2!=null,则比较l1和l2指向的元素大小,若l1小于于等于l2,则p=l1,指针l1向后移动一个位置,否则p=l2,指针l2向后移动一个位置。
对于第4中情况:
将head赋值给一个新的节点p用于合拼操作的情况
4.1 迭代:当当前的l1和l2都不为null的时候,比较大小,若l1小于于等于l2,则p = l1,l1 = l1.next,p = p.next;否则p = l2,l2 = l2.next,p=p.next;
4.2 当上面的迭代循环完成时,如l1==null,说明链表l1指向的链表已经全部合并,此时应该让指针p指向l2指向的剩余第二个链表的部分:p.next = l2;同理也有p.next = l1;
算法最后返回头节点head即可
代码如下:
/** * Definition for singly-linked list. * public 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) { ListNode head = list1; //若l1==null && l2 == null,则合并的链表自然为空 if(list1 == null && list2 == null){ return head; } // 若l1 == null && l2 != null,则合并的链表即为l2,返回l2即可 if(list1 == null && list2 != null){ return list2; } // 若l1 != null && l2 == null,则合并的链表即为l1,返回l1即可 if(list1 != null && list2 == null){ return head; } // 上面的情况都没有满足的情况自然是l1 != null && l2!=null,则比较l1和l2指向的元素大小 // 确定头节点 if(list1.val<= list2.val){ head = list1; // 指针往后一步 list1 = list1.next; }else { head = list2; // 指针前进一步 list2 = list2.next; } ListNode p = head; //从头节点指针p开始操作 while(list1!= null && list2!= null){ if(list1.val<= list2.val){ // 如果要在这里确定头节点,p = list1,操作是不统一的,需要分开判断 p.next = list1; list1 = list1.next; }else { p.next = list2; list2 = list2.next; } p = p.next; } if(list1 == null){ p.next = list2; } if(list2 == null){ p.next = list1; } return head; } }
从上面的代码,我们也可以看出有很多判断链表是否为空链表的操作,判断空指针的操作,此时如果我们使用虚拟头节点的时候,
就不需要这么多的判断的操作了也不需要再对头节点单独进行操作,
操作是不统一的,需要分开判断
此外,在对两个链表的操作的过程中,balalala的,不应该在头节点指针list1和list2上操作,应该重新创建新指针指向两个链表再进行操作:
加上虚拟节点
改进的代码如下:
/** * Definition for singly-linked list. * public 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) { // 虚拟节点 ListNode dumpy = new ListNode(-1); ListNode p = dumpy; ListNode p1 = list1,p2 = list2; //从头节点指针p开始操作 while(p1!= null && p2!= null){ if(p1.val<= p2.val){ p.next = p1; p1 = p1.next; }else { p.next = p2; p2 = p2.next; } p = p.next; } if(p1 == null){ p.next = p2; } if(p2 == null){ p.next = p1; } return dumpy.next; } }
这篇关于[Leetcode]21. 合并两个有序链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升