1. 原题链接
https://leetcode.com/problems/merge-two-sorted-lists/description/
2. 题目要求
给出两个已经从小到大排序的链表ls1、ls2，进行合并，合并后仍有序，返回合并后的链表
3. 解题思路
创建一个表头指针headPointer和一个定位指针locatePointer，headPointer用来保存头结点。
同时对ls1和ls2进行遍历，当ls1的值小于ls2的值时，locatePointer指向ls1，否则指向ls2。
当一个链表为空另一个不为空，则将不为空链表的剩余结点依次加入新的链表。
4. 代码实现
public class MergeTwoSortedList {
public static void main(String[] args) {
ListNode ls1 = new ListNode(-9);
ListNode ls2 = new ListNode(3);
ListNode ls3 = new ListNode(4);
ListNode ls4 = new ListNode(5);
ListNode ls5 = new ListNode(7);
ListNode ls6 = new ListNode(8);
ls1.next = ls2;
ls2.next = ls3;
ls4.next = ls5;
ls5.next = ls6;
ListNode ls = mergeTwoLists(ls1, ls4);
while (ls != null) {
System.out.println(ls.val);
ls = ls.next;
}
}
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode headPointer = new ListNode(-1);
ListNode res = headPointer;
while (l1 != null || l2 != null) {
if (l1 != null && l2 == null) {
res.next = l1;
l1 = l1.next;
} else if (l1 == null && l2 != null) {
res.next = l2;
l2 = l2.next;
} else {
if (l1.val < l2.val) {
res.next = l1;
l1 = l1.next;
} else {
res.next = l2;
l2 = l2.next;
}
}
res = res.next;
}
return headPointer.next;
}
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}