Leetcode原题
思路
其实我本人对链表这一块学得挺模糊的。我们知道链表有分单链表、双链表、循环链表。
单链表的Node数据结构，是一个元素data，和存储指向下一个节点的next。这一道题刚好是单链表入门题。
方法1 循环双指针法
我们可以设立一个哨兵节点result，用于方便返回合并后的链表。并维护一个指针pre，只要不断的操作这个指针，分别比较 l1 和 l2 两个链表头节点的值，谁的值小，pre就将指针指向较小的一方，同时不断的更新l1,l2的节点值。直到l1或l2指向空。在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这时我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
//循环双指针方法 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 ==null) return l2; //处理空的情况 if (l2 ==null) return l1; ListNode resultNode=new ListNode(0); ListNode pre =resultNode; while (l1!=null && l2!=null){ if (l1.val<l2.val){//若l1的值小于l2.则指针指向l1 ，且l1自己往后挪 pre.next =l1; l1 =l1.next; }else{ //若l2的值小于l1.则指针指向l2 ，且l2自己往后挪 pre.next =l2; l2 =l2.next; } pre =pre.next; } if(l1!= null){ pre.next =l1; } if (l2!= null){ pre.next =l2; } return resultNode.next; }
方法2 递归
参考官网提示，如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
//方法2 递归的形式 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 ==null) return l2; //处理空链表的情况 if (l2 ==null) return l1; if (l1.val<l2.val){ l1.next = mergeTwoLists(l1.next,l2); return l1; } l2.next = mergeTwoLists(l1,l2.next); return l2; }
提交记录
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
