【Hot100】LeetCode—21. 合并两个有序链表

---

• 原题连接：21. 合并两个有序链表

---

1- 思路

思路

思路如下 ：①定义四个指针、②通过判断两个 list的指针结果 、③移动 三个指针来收集结果

• ① 定义四个指针
  • curA 和 curB 分别用来遍历 list1 和 list2
  • dummyHead 用来记录头结点
  • cur 用来记录合并后的链表的当前结点
• ② 利用 while 循环遍历两个链表：移动三个指针
• ③ 最终结果，判断curA 和 curB哪个未遍历完，直接拼接在 cur 后面即可

---

2- 实现

⭐21. 合并两个有序链表——题解思路

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode curA = list1;ListNode curB = list2;ListNode dummyHead = new ListNode(-1);ListNode cur = dummyHead;while(curA!=null && curB!=null){if(curA.val < curB.val){cur.next = curA;curA = curA.next;}else{cur.next = curB;curB = curB.next;}cur = cur.next;}if(curA !=null){cur.next = curA;}if(curB !=null){cur.next = curB;}return dummyHead.next;}
}

---

3- ACM 实现

public class mergeList {public static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public static ListNode mergeList(ListNode list1,ListNode list2){// 1.数据结构ListNode curA = list1;ListNode curB = list2;ListNode dummyHead = new ListNode(0);ListNode cur = dummyHead;while(curA!=null && curB!=null){if(curA.val < curB.val){cur.next = curA;curA = curA.next;}else{cur.next = curB;curB = curB.next;}cur = cur.next;}if(curA!=null){cur.next = curA;}if(curB!=null){cur.next = curB;}return dummyHead.next;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);
// 读取第一个链表的节点数量int n1 = sc.nextInt();ListNode head1 = null, tail1 = null;for (int i = 0; i < n1; i++) {int val = sc.nextInt();ListNode newNode = new ListNode(val);if (head1 == null) {head1 = newNode;tail1 = newNode;} else {tail1.next = newNode;tail1 = newNode;}}// 读取第二个链表的节点数量int n2 = sc.nextInt();ListNode head2 = null, tail2 = null;for (int i = 0; i < n2; i++) {int val = sc.nextInt();ListNode newNode = new ListNode(val);if (head2 == null) {head2 = newNode;tail2 = newNode;} else {tail2.next = newNode;tail2 = newNode;}}ListNode forRes = mergeList(head1,head2);while(forRes!=null){System.out.print(forRes.val+" ");forRes = forRes.next;}}}