合并有序链表

1、参考资料

https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d

2、题目要求

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，即不开辟新的内存空间

3、代码思路

首先，为了方便操作链表，我们定义一个 dummyHead，我们遍历两个链表，直到其中有一个到达尾部，则停下来

在遍历的过程中，我们将元素值小的节点依次链在 mergerList 的后边，最后，我们看看哪个链表还有剩余的节点，将其链在 mergeList 的后边，最后返回合并链表的首节点

4、代码实现

代码

static class Solution { /** * 合并两个有序链表 * * @param list1 ListNode类 * @param list2 ListNode类 * @return ListNode类 */ public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummyHead = new ListNode(0); // 合并后链表的头结点 ListNode mergeListPointer = dummyHead; // 合并链表的指针 ListNode list1Poniter = list1; // list1 的指针 ListNode list2Poniter = list2; // list2 的指针 // 任意一个链表到尾部，则停止循环 while (list1Poniter != null && list2Poniter != null) { // 将小的元素接到 mergeList 的后面 if (list1Poniter.val < list2Poniter.val) { mergeListPointer.next = list1Poniter; list1Poniter = list1Poniter.next; // 指针后移 } else { mergeListPointer.next = list2Poniter; list2Poniter = list2Poniter.next; // 指针后移 } mergeListPointer = mergeListPointer.next; // 指针后移 } // 看看哪个链表还有剩余的部分，将它接在 mergeList 的后面 if (list1Poniter != null) { mergeListPointer.next = list1Poniter; } else { mergeListPointer.next = list2Poniter; } // 返回合并后链表的首结点 return dummyHead.next; } } static class ListNode { int val; ListNode next = null; public ListNode(int val) { this.val = val; } }