合并两个排序的链表

Easy 原题连接：合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

  • 0 <= 链表长度 <= 1000

解题思路

并行比较两边的大小，依次遍历相接

  1. 对于判空，用于开始判空，如果原本的 l1 或 l2 就存在空，直接返回。也可以在遍历时，其中一边已经完成遍历全部进入排序，判空使剩下数组快速进入排序
  2. 对于比大小，首次比大小决定是使用 l1 还是 l2 作为最后组合排序的结果返回，后续遍历作为后接链表的判断

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)  return l2;
        if(l2 == null)  return l1;
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }   
    }
}

两个链表的第一个公共节点

Easy 原题连接：两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

示例：

4 → 1 → 8 → 4 → 5
        ↑
5 → 0 → 1     
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

限制：

  • 如果两个链表没有交点，返回 null.

  • 在返回结果后，两个链表仍须保持原有的结构。

  • 可假定整个链表结构中没有循环。

  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路

首先，假定两个链表一定有交点，那么这整个结构可以被分为三个部分：

  1. 链表1不重复的部分，长度a
  2. 链表2不重复的部分，长度b
  3. 链表1和链表2重复部分，长度c

限制中程序需要尽量满足O( n )时间复杂度，所以只不能对其中一边遍历：对链表1和链表2走相同长度遍历到相交节点

只单独遍历两个链表自然是不大可能做到恰好a与b长度一致而返回节点，那不妨”链接“两个链表

对于链表1，在遍历完成后，继续遍历链表2，遍历长度：a+c+b+c

对于链表2，在遍历完成后，继续遍历链表1，遍历长度：b+c+a+c

通过上述两个式子，不难看出，如果同步遍历的话，其实只要走 a+c+b ( b+c+a )的长度就会相遇，也就是第二次遇到相交节点时相遇

不过还有另一种可能：两个链表没有相交

对于链表1，在遍历完成后，继续遍历链表2，遍历长度：a+b

对于链表2，在遍历完成后，继续遍历链表1，遍历长度：b+a

最后发现两边都为null，那就返回null

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode A = headA, B = headB;
        while(A != B) {
            A = A!=null ? A.next : headB;
            B = B!=null ? B.next : headA;
        }
        return A;
    }
}

扩展：判断一个可能带环的链表，入环节点在哪

印象里的一个题，做第二题的时候想到了，就顺带记录一下

题目：给你一个链表，它可能带环（也可能不带），如果它带环，请返回入环节点，如果不带环，请返回null

限制：如果带环，一定存在入环节点（不会是一整个环）

思路：使用快慢指针，如果快指针指到null，说明不带环；如果快慢指针相遇，将快指针指回开头，以慢指针的步调与慢指针一起移动，下次相遇一定是入环节点

Java代码：

class Solution {
    ListNode fun(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return null;
        // A作为慢指针，B作为快指针
        ListNode A = head.next, B = head.next.next;
        while(A != B) {
            if(B.next != null && B.next.next != null) {
                return null;
            }
            A = A.next;
            B = B.next.next;
        }
        B = head;
        while(A != B) {
            A = A.next;
            B = B.next;
        }
        return A;
    }
}

数学证明：

1 → 2 → 3 → 4 → 5

​ ↑ ↓

​ 7 ← 6

以这个环为例：首次快慢指针相交会指向6，加上入环节点，整个结构需要注意三个部分长度：

  1. 入环前长度：a （1 - 2 - 3）
  2. 入环至相交的长度：b （3 - 4 - 5 - 6）
  3. 环的长度：c （3 - 4 - 5 - 6 - 7 - 3 ）

首次相交，快指针走了：a + c + b，慢指针走了：a + b，我们得到：a + c + b = 2（a + b）,即 c = a + b

将快指针重置会头节点，再次走向入环节点，需要走：a

此时的慢指针走向入环节点，需要走：c - b = a

综上，证明成功