【DS】链表面试热题之合并链表及其变体

---

合并有序链表核心思路：

双指针：分别遍历两个链表，然后链到总的链表上。

---

模板：

ListNode head = new ListNode(-1);
ListNode prev = head;
while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) {
        prev.next = list1;
        list1 = list1.next;
    } else {
        prev.next = list2;
        list2 = list2.next;
    }
    prev=prev.next;
}
prev.next=(list1==null)?list2:list1;
return head.next;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

一、合并两个有序链表

题目描述

1.输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。OJ链接

思路分析：

1. 比较两个链表当前引用的val值小的加入总的链，循环比较操作，循环条件是两个引用都不是空的，否则容易空指针异常。
2. 循环终止的时候，肯定有一个结点不是空的这个时候我们需要单独操作，，然后让总的遍历的pre链上它
3. 为了方便操作这里引用了一个虚拟头结点，返回的时候只要返回它的next值即可

图示分析：

AC代码

public ListNode Merge(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode prev = head;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            prev.next = list1;
            list1 = list1.next;
        } else {
            prev.next = list2;
            list2 = list2.next;
        }
        prev=prev.next;
    }
    prev.next=(list1==null)?list2:list1;
    return head.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、合并k个有序链表

题目描述

2.合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。OJ链接

思路分析：

1. 给的顺序表，顺序表中的每个值是链表的每个头结点，所以循环条件是顺序表不为空
2. 一个一个从表中拿出来，在调用我们之前定义的合并两个有序链表肯定行不通，这样不满足时间复杂度为O(nlogn)，行不通。

几点注意：

1. 注意导包
2. int mid = left + (right - left) /2;可以通过，但是int mid = left + (right - left)>>1;没办法通过，原因未知，以后再说。

图示分析：

AC代码

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    return divideMergeLists(lists,0,lists.size()-1);
}
private ListNode divideMergeLists(ArrayList<ListNode> lists, int left,int right) {
    if (left > right) {
        return null;
    } else if (left == right) {
        return lists.get(left);
    }
    int mid = left + (right - left) /2;
    return Merge(divideMergeLists(lists, left, mid), divideMergeLists(lists, mid+1, right));
}
private ListNode Merge(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode prev = head;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            prev.next = list1;
            list1 = list1.next;
        } else {
            prev.next = list2;
            list2 = list2.next;
        }
        prev = prev.next;
    }
    prev.next = (list1 == null) ? list2 : list1;
    return head.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28