题解 | #合并两个排序的链表03#
合并两个排序的链表
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode res = dummy;
// 必须保证两个list都不为空
while(list1 != null & list2 != null) {
if(list1.val > list2.val) {
dummy.next = list2;
list2 = list2.next;
dummy = dummy.next;
} else if(list1.val <= list2.val) {
dummy.next = list1;
list1 = list1.next;
dummy = dummy.next;
}
}
// list1后面还有，就把剩下的全部拿走
if(list1 != null) {
dummy.next = list1;
}
if(list2 != null) {
dummy.next = list2;
}
return res.next;
}
}
- 创建一个虚拟结点和一个哨兵结点
- 当list1与list2都不为null时循环
- 哪个的val小哪个赋给虚拟结点的next，虚拟结点后移。
- 退出循环后，哪个list不为空，哪个结点（包括剩下的）给虚拟结点的next
- 最后返回哨兵结点的next
注意这个哨兵节点！！！！他只对dummy.next被改变时敏感 dummy本身被赋值与res无关
）。