问题: 合并两个有序链表
链表L1: 1->2->4->9
链表L2: 3->5>6->10->13
合并后:1->2->3->4->5->6->9->10->13
1. 准备数据结构 及测试数据
Node节点
public class Node { public Integer value; public Node next; // 构造 public Node(){} public Node(Integer value) { this.value = value; } public Node(Integer value,Node next) { this.value = value; this.next = next; } // 打印链表 public void print() { Node n = this; System.out.println("------------------------------------------------"); while (n != null) { System.out.print(n.value); n = n.next; if (n != null) { System.out.print("-->"); } else { System.out.println(); } } System.out.println("------------------------------------------------"); } }
准备测试数据
public class TestNode { public static void main(String[] args) { Node L1= getL1(); Node L2= getL2(); // 1-->2-->4-->9 L1.print(); // 3-->5-->6-->10-->13 L2.print(); } // 获取测试数据L1 public static Node getL1() { Node head = new Node(1,new Node(2,new Node(4,new Node(9)))); return head; } // 获取测试数据L2 public static Node getL2() { Node head = new Node(3,new Node(5,new Node(6,new Node(10,new Node(13))))); return head; } }
2.解决方案01
定义一个伪头节点Head 然后遍历L1 L2 比较Node值 小的就追加到Head后边
private static Node mergeNodes(Node l1, Node l2) { if (l1 == null ){ return l2; } if (l2 == null) { return l1; } // 链表头 Node head ; // 新链表添加的当前位置 Node next ; // 先选出一个2个链表开头的最小值 head = next = l1.value > l2.value ? l2:l1; // 头指针向后移动 l1 = head == l1 ? l1.next : l1; l2 = head == l2 ? l2.next : l2; // 遍遍历2个链表 while (l1 !=null && l2 != null) { // 遍历链表的最大值 Node maxNode = null; // 链表1值大 if(l1.value <= l2.value) { maxNode = l1; l1 = l1.next; } else { // 链表2值大 maxNode = l2; l2 = l2.next; } // 添加到新链表 next向后移 next.next = maxNode; next = next.next; } // 判断哪个链表还没有遍历完 直接加到新链表末尾 next.next = l1 == null ? l2 :l1; // 返回head return head; }
3.解决方案02
定义一个伪头节点Head 然后遍历L1 L2 比较Node值 小的就追加到Head后边
使用递归 不用while循环
private static Node mergeNodesRec(Node l1, Node l2) { // 如果l1 链表已经遍历完了 if (l1 == null) { return l2; } // 如果l2 链表已经遍历完了 if (l2 == null) { return l1; } Node head ; if(l1.value <= l2.value) { head = l1; l1 = l1.next; } else { head = l2; l2 = l2.next; } // 递归调用 设置next head.next = mergeNodesRec(l1,l2); return head; }
自己写一写、用笔画一画 可能会豁然开朗 肯定还有其他写法 欢迎留言
欢迎关注公众号: