21. 合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
使用指针或者递归可解,其中指针方式更加容易理解,通过一个哨兵节点来连接两个链表的节点。如果采用递归,实际上下面案例中两种递归的思想是一的,只不过递归2的写法更简单而已。
- 1 方式一 指针
- 2 方式二 递归一
- 3 方式三 递归二
public class LeetCode21{ public ListNode mergeTwoLists( ListNode list1, ListNode list2 ){ //通过一个哨兵节点来连接两个链表的节点 ListNode dummy = new ListNode( 0 ); ListNode pre = dummy; while( list1 != null && list2 != null ){ //比较大小,谁更小,那么谁就是成为pre的后继,并且更新该引用的指向 if( list1.val >= list2.val ){ pre.next = list2; list2 = list2.next; } else{ pre.next = list1; list1 = list1.next; } //更新pre的指向 pre = pre.next; } //需要注意剩下还未追加的部分节点 pre.next = list1 == null ? list2 : list1; return dummy.next; } 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; } } }2 方式二 递归一
public class LeetCode21{ public ListNode mergeTwoLists1( ListNode list1, ListNode list2 ){ if( list1 == null || list2 == null ){ return list1 == null ? list2 : list1; } if( list1.val > list2.val ){ //返回一个大于当前小节点的最小节点,成为当前小节点的后继 list2.next = mergeTwoLists1( list1, list2.next ); //返回小节点 return list2; } else{ //返回一个大于当前小节点的最小节点,成为当前小节点的后继 list1.next = mergeTwoLists1( list1.next, list2 ); //返回小节点 return list1; } } 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; } } }3 方式三 递归二
public class LeetCode21{ public ListNode mergeTwoLists2( ListNode list1, ListNode list2 ){ if( list1 == null || list2 == null ){ return list1 == null ? list2 : list1; } //获取较小的节点 ListNode min = list1.val > list2.val ? list2 : list1; min.next = mergeTwoLists2( min.next, min == list1 ? list2 : list1 ); //返回小节点 return min; } 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; } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)