算法09(链表)-合并两个链表

算法双指针链表

发布时间 : 2020-07-04 16:14

字数:535 阅读 :

题目：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4 —->l1
输出：1->1->2->3->4->4—->l2

解法1：暴力解法：因为l1和l2两个链表是升序排列顺序已经固定了的，一个指针指向l1的head,一个指针指向l2的头指针，如果l1.val<l2.val，定义一个哑结点，将哑结点的next指向l1,并且移动哑结点指针，同时移动l1的指针指向，如果条件不成立，将哑结点的下一个结点指向l2 ,并且移动哑结点指向，同时移动l2的指向下一个。
代码设计如下：
ListNode类

package com.cxy.linkedtable;


/**
 * 结点类
 */
public class ListNode {
  int val;
  //指向结点指针
  ListNode next;
  //
  public ListNode(int val){
    this.val = val;
  }
  public ListNode(int currData,ListNode next){
    this.val = currData;
    this.next = next;
  }
  public ListNode(){}

  @Override
  public String toString() {
    ListNode head = this;
    StringBuilder s = new StringBuilder();
    while (head != null){
      s.append(head.val+ " ");
      head = head.next;
    }
    return s.toString();
  }
}

逻辑实现类

package com.cxy.linkedtable;

import javax.swing.*;

public class MergTwoLTable {
  public ListNode mergeTwoLists(ListNode l1,ListNode l2){
    //创建一个哑结点()
    ListNode dummp = new ListNode(-1);
    ListNode curr = dummp;
    if(l1 == null){return l2;}
    if(l2 == null){return l1;}
    while(l1 != null && l2 != null){
      if(l1.val < l2.val){
        curr.next = new ListNode(l1.val);
        //移动l1,指向下一个结点
        l1 = l1.next;
      }else {
        curr.next = new ListNode(l2.val);
        l2 = l2.next;
      }
      //移动当前指针到下一个结点
      curr = curr.next;
    }
    if(l1 == null){curr.next = l2;}
    if(l2 == null){curr.next = l1;}
    return dummp.next;
  }

  public static void main(String[] args) {
    MergTwoLTable lTable = new MergTwoLTable();
    ListNode l1 = new ListNode(1);
    l1.next = new ListNode(2);
    l1.next.next = new ListNode(4);
    ListNode l2 = new ListNode(1);
    l2.next = new ListNode(3);
    l2.next.next = new ListNode(4);
    ListNode node = lTable.mergeTwoLists(l1, l2);
    System.out.println(node.toString());
  }
}

本题采用暴力解法，效率不是很高，听官方讲可以采用递归，具体代码可以参考下面代码
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com