题解 | #合并两个排序的链表#
合并两个排序的链表
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ /** 思路解析:(前提是两个链表均是有序的) 1.首先对于特殊情况的链表做出判断,如果其中一个为空,那么两表合并必为其中一个的原链表 2.创建新链表,用于保存两个链表的结合,设置为以head节点开头,后期用于返回合并链表的头节点,在这里使用cur保存head节点,为的是用于两表合并应该存放在新链表的位置 3.核心代码逻辑部分,只要两个链表不为空,那么就一直遍历,在循环中做出判断,两个链表的当前头节点val部分值的大小,小的优先放进新链表中,待不满足条件(比如其中一个链表的节点为null了),就跳出循环 4.做一些收尾操作,比如有一个链表的节点不为null,那么我们就要将剩余的节点与我们新的链表做一个指针的引用,指向旧链表当前节点的位置 */ public class Solution { public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } //-------------------------以上为第一部分-------------------------------------- ListNode head = new ListNode(0); ListNode cur = head; //-------------------------以上为第二部分-------------------------------------- while (list1 != null && list2 != null) { if (list1.val > list2.val) { cur.next = list2; list2 = list2.next; } else { cur.next = list1; list1 = list1.next; } cur = cur.next; } //-------------------------以上为第三部分-------------------------------------- if (list1 != null) { cur.next = list1; } else { cur.next = list2; } //-------------------------以上为第四部分-------------------------------------- return head.next; //返回头节点的下一个节点是因为我们使用的节点确实是从head的下一个节点开始的 } }#链表类型#