2.3 链表-2条.md

链表-2条

链表的结点定义为：

struct ListNode
{
  int m_nKey;
  ListNode* m_pNext;
};

找出两个链表的第一个公共结点

题目：两个单向链表，找出它们的第一个公共结点。

分析：第一个公共节点，也就是2个链表中的节点的m_pNext 指向的同一个节点。 2遍遍历方法：

1. 先遍历2个链表，得到各自的长度，和差sub
2. 长链表先遍历sub个节点，然后2个节点一起遍历
3. 第一次同时指向的同一个节点就是这个commonNode

有没有可能一遍遍历就解决问题呢？

让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。 空间复杂度为 O(1)，时间复杂度为 O(N), 一遍遍历就搞定

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;

    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;

        else            p1 = p1.next;
        
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    
    return p1;
}

判断俩个链表是否相交

给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。

问题扩展：

1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列?

合并2条有序链表

while 循环每次比较 p1 和 p2 的大小，把较小的节点接到结果链表上

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;

    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }

    if (p1 != null) {
        p.next = p1;
    }

    if (p2 != null) {
        p.next = p2;
    }

    return dummy.next;
}

合并k个有序链表

相比合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？

就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点：

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列，最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

输出两个非降序链表的并集

请修改append函数，利用这个函数实现：

两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5 。另外只能输出结果，不能修改两个链表的数据。