合并两个有序链表

• 力扣第21题
• 题目地址：
• https://leetcode-cn.com/problems/merge-two-sorted-lists/
• 题目描述：
• 将两个升序链表合并为一个新的升序链表并返回。
• 新链表是通过拼接给定的两个链表的所有节点组成的。

题解：

1. 给你两个有序链表
2. 合并为一个有序链表

可以简单理解为： 同时遍历两个链表， 当前遍历的结点，谁的结点小，就把谁的结点“摘下来”，“安装”在新链表上就可以了吧。

这里为了简单方便的处理， 给新链表先“安装”一个头结点

将 l2 链表的 1 结点摘下来，放到新链表的尾部。
将 l2 链表的 2 结点摘下来，放到新链表的尾部。
将 l1 链表的 3 结点摘下来，放到新链表的尾部。
同理…
l2 链表被摘完了， l2 == null

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode newhead = new ListNode(); ListNode tail = newhead; while( list1 != null && list2 != null ){     if (list1.val < list2.val){  tail.next = list1;  list1 = list1.next;     }else{  tail.next = list2;  list2 = list2.next;     }     tail = tail.next; } if (list1 != null) tail.next = list1; if (list2 != null) tail.next = list2; return newhead.next;    }

为了便于测试，阿红也写了添加节点、和遍历节点的方法。

上代码

package leetcode.link;/** * 力扣第21题 * 题目地址： * https://leetcode-cn.com/problems/merge-two-sorted-lists/ * 题目描述： * 将两个升序链表合并为一个新的升序链表并返回。 * 新链表是通过拼接给定的两个链表的所有节点组成的。 */public class _21_MergeTwoLists {    ListNode head = null;    int size = 0;    public static class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) {     this.val = val; } ListNode(int val, ListNode next) {     this.val = val;     this.next = next; }    }    public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode newhead = new ListNode(); ListNode tail = newhead; while( list1 != null && list2 != null ){     if (list1.val < list2.val){  tail.next = list1;  list1 = list1.next;     }else{  tail.next = list2;  list2 = list2.next;     }     tail = tail.next; } if (list1 != null) tail.next = list1; if (list2 != null) tail.next = list2; return newhead.next;    }    /**     * 头插法     * @param element     */    public void addhead(int element){ ListNode node = new ListNode(element,head); head = node; size++;    }    /**     * 尾插法     * @param val     */    public void add(int val){ if ( head == null ){     //头指针为空时，让头指正指向第一个插入的节点     ListNode tail = new ListNode(val,head);     head = tail; }else{     ListNode node = head;     while(node.next != null){  node = node.next;     }     node.next = new ListNode(val,null); } size++;    }    public String toString(){ StringBuilder str = new StringBuilder(); ListNode node = head; str.append("size: " + size +" ["); for (int i = 0 ; i ");     }     node = node.next; } str.append("]"); return str.toString();    }    public static void main(String[] args) { _21_MergeTwoLists list = new _21_MergeTwoLists(); list.add(0); list.add(2); list.add(4); System.out.println(list); _21_MergeTwoLists list2 = new _21_MergeTwoLists(); list2.add(2); list2.add(3); System.out.println(list2); _21_MergeTwoLists lists = new _21_MergeTwoLists(); ListNode head =  lists.mergeTwoLists(list.head,list2.head); while(head != null){     System.out.println(head.val);     head = head.next; }    }}

测试结果