【算法-简单01】合并2个有序数列

合并2个有序数列

• 结果：

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)

• 比较抽象的点

  • 结论：Node对象有3个属性：Node本身、val，以及Node.next
    • Node本身判空，结合while来进行遍历查询
    • val大小判断，来进行ab -> ba，保证指针遍历的方向是递增的
    • Node.next判空，用来判断传递指针的边界
  • 问题：在哪一步运用迭代？迭代过程主要做什么事情？迭代结束又要做什么事情？在哪里返回List？怎么保证从小到大的顺序是正确的？又如何判断迭代何时结束？
    • 先从简单的例子开始观察
    • 其中的最小组合ab
      • ab要判断大小
      • ab要判断是否含有next
      • 假定a<=b，否则二者换顺序
      • 判断到最后，发现就是间隔最小的2个！
      • 链接即可
      • 自动迭代
  • 草图
    
  • 迭代的逻辑：a.next=M(a,b)：
    • 默认a<=b,否则就换顺序，这里会增加空间复杂度吗？
    • 如果a<=b，就比较M(a.next,b)。因为上一条的逻辑，M一定可以按正确的顺序迭代到尽头
    • 到了尽头、即不存在next了，通过null = a.next来判断
    • a.next=b完成最后一个元素的链接
  • 延伸：如果2个list都是无序的呢？
    • 方案一：先对每个list自己排序，再调用上面的合并方法
    • 方案二：再想……

• 实现方法：将添加、遍历、合并分成三个方法， 以免过于纠缠

  • 先构建基本的ListNode对象

  //构建测试方法
  
  //构建基本的Node对象
  package collections;
  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; }
  
  }
  

  • 再构建测试类ListTest对象

  package collections;
  import org.junit.Test;
  public class ListTest {
      @Test
      public void testList(){
          int[] a = {9,19,20,25,29};
          int[] b = {11,22,28,100};
          ListNode list1 = addNode(a);
          ListNode list2 = addNode(b);
          try{
          ListNode list = mergeTwoLists(list1,list2);
          printNode(list);
          }catch (Exception e){
              e.printStackTrace();
          }
      }
  }
  

  • 构建方法：实现Array -> ListNode

  public ListNode addNode(int[] ints){
      ListNode pointer = new ListNode();
      ListNode list1 = pointer;
      //构造ListNode
      for(int i = 0;i<ints.length-1;i++){
          pointer.val = ints[i];
          pointer.next = new ListNode(ints[i+1]);
          pointer = pointer.next;
      }
      //调用方法，遍历ListNode
      System.out.println("添加的List长度是："+ints.length);
      printNode(list1);
      return list1;
  }
  

  • 构建方法：遍历ListNode

  public void printNode(ListNode node){
      ListNode testNode = node;
      System.out.println("ListNode遍历如下：");
      while(null!=testNode){
          System.out.println(testNode.val);
          testNode = testNode.next;
      }
  }
  

  • 构建方法：合并2个ListNode

  public ListNode mergeTwoLists(ListNode list1,ListNode list2){
      //先判断是否有next，有就迭代指针，没有就追加
      //value仅用来判断大小,交换位置，确保左小右大
      if(list1.val>list2.val){
          ListNode listNode = new ListNode();
          listNode = list1;
          list1 = list2;
          list2 = listNode;
      }
      if(null!=list1.next){
          //非常关键的一步迭代，迭代的意义仅仅是按正确的顺序传递指针
          list1.next = mergeTwoLists(list1.next,list2);
          System.out.println("指针传递到："+list1.next.val);
      }else{
          //迭代的尽头就找到了最小间隔a和b，必要的操作是给二者添加链接
          //（删除线，中间的调序操作已经随着每次迭代进行判定和操作了，否则无法找到正确的顺序方向）找到尽头之后，会按指针传递的顺序反向、逐个操作添加链接，完成合并
          //找到尽头后，最后2个元素完成链接，迭代结束，返回list
          list1.next = list2;
          System.out.println("追加了"+list2.val);
      }
      return list1;
  }