数据结构与算法 | Leetcode 21:Merge Two Sorted Lists

原文链接：https://wangwei.one/posts/jav…前面，我们实现了链表的 环检测 操作，本篇来聊聊，如何合并两个有序链表。有序链表合并Leetcode 21:Merge Two Sorted Lists示例Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4使用虚假的Head节点定义一个临时虚假的Head节点，再创建一个指向tail的指针，以便于在尾部添加节点。对ListNode1和ListNode2同时进行遍历，比较每次取出来的节点大小，并绑定到前面tail指针上去，直到最终所有的元素全部遍历完。最后，返回 dummyNode.next ，即为新链表的head节点。代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } /class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyNode = new ListNode(0); ListNode tail = dummyNode; while(true){ if(l1 == null){ tail.next = l2; break; } if(l2 == null){ tail.next = l1; break; } ListNode next1 = l1; ListNode next2 = l2; if(next1.val <= next2.val){ tail.next = next1; l1 = l1.next; }else{ tail.next = next2; l2 = l2.next; } tail = tail.next; } return dummyNode.next; } }递归使用递归的方式，代码比遍历看上去简洁很多，但是它所占用的栈空间会随着链表节点数量的增加而增加。代码/* * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode result = null; if(l1 == null){ return l2; } if(l2 == null){ return l1; } if(l1.val <= l2.val){ result = l1; result.next = mergeTwoLists(l1.next, l2); }else{ result = l2; result.next = mergeTwoLists(l1, l2.next); } return result; } }