有环或无环链表的相交问题（链表中的爹题）_C

1、题目

给定两个可能有环也可能无环的单链表，头结点 head1 和 head2。请实现一个函数，如果两个链表相交，返回相交的第一个节点；如果不相交，返回 null。

要求：如果两个链表长度之和为 N N N，时间复杂度请达到 O ( N ) O(N) O(N)，额外空间复杂度请达到 O ( 1 ) O(1) O(1)

2、思路

先判断链表是否有环，如果链表无环，返回空；如果链表有环，返回第一个入环节点；
- 方法1：使用容器，准备一个哈希表，遍历链表，如果遍历到节点node，查询哈希表发现该节点在表中，则这个节点是第一个入环节点；
- 方法2：不使用容器，仅使用几个有限的变量。准备快慢两个指针，快指针每次走2步，慢指针每次走1步，如果两个指针相遇，则表明链表有环；然后将快指针指向头结点，慢指针保持不变，两个指针每次同时走1步，再次相遇的位置就是入环节点。
再考虑链表相交的问题：链表1的入环节点 loop1，链表2的入环节点 loop2
- 情况1：如果两个链表都是无环的（即 loop1 = loop2 = nullptr），判断相交；如果相交找到第一个相交节点
  - 方法1：使用容器 set，先遍历链表1的每个节点，放入 set 中；然后遍历链表 2 的每个节点，查询是否在 set 中，如果在，则说明两个链表相交；
  - 方法2：不使用容器。
    
    ① 首先遍历链表 1，记录其长度 len1 和最后一个节点 end1；然后遍历链表 2，记录其长度 len2 和最后一个节点 end2。
    
    ② 如果 end1 != end2 ，则两个链表不相交；如果 end1 = end2，说明两个链表一定相交，且 end1/ end2 是最后一个相交节点。
    
    ③但是现在要找的是相交的第一个节点。解决方法：假设链表 1 有 100 个节点，而链表 2 有 80 个节点，让链表 1 先走20步，然后两个链表同时以每次前进 1 步的节奏移动，那么它们一定会在相交的第一个节点处相遇。
- 情况2：一个链表有环，一个链表无环，这种情况不可能相交
- 情况3：两个链表都有环的情况（即 loop1 != nullptr && loop2 != nullptr)
  - ①两个链表都各自有环，且不相交
  - ②两个链表相交，且两个链表的入环节点是同一个（loop1 = loop2，就认为 loop1 和 loop2 是终止节点，问题就变成了两个无环链表找第一个相交节点）
  - ③两个链表相交，但两个链表的入环节点不是同一个
  上述三种情况的图示：
  
  对于情况①和③，从 loop1 出发，如果转一圈回到了自己，且在这个过程中没有遇到 loop2，那么就是情况①，不相交，返回空；如果转一圈的过程中碰到了 loop2，那就是情况③，这种情况下 loop1 和 loop2 都是第一个相交节点，只是 loop1 离链表1 更近，loop2 离链表 2 更近，返回二者任意一个都可以。

3、实现 C++ 版

/*************************************************************************
	> File Name: 025.链表相交问题.cpp
	> Author: Maureen
	> Mail: [email protected]
	> Created Time: 三  6/15 16:56:27 2022
 ************************************************************************/

#include 
using namespace std;


class Node {
public:
    int value;
    Node *next;
    Node(int v) : value(v) {}
};

//判断链表是否有环，如果有环返回入环节点，否则返回空
Node *getLoopNode(Node *head) {
    Node *slow = head;
    Node *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) { //存在环
            fast = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }

    return nullptr;
}


//两个链表都是无环的，判断是否相交，如果相交则返回第一个相交节点
Node *noLoop(Node *head1, Node *head2) {
    int n = 0;
    Node *cur1 = head1;
    Node *cur2 = head2;

    while (cur1->next != nullptr) {
        n++;
        cur1 = cur1->next;
    } //此时cur1为链表1的尾结点

    while (cur2->next != nullptr) {
        n--;
        cur2 = cur2->next;
    } //此时cur2为链表2的尾结点

    //两个链表不相交
    if (cur1 != cur2) return nullptr;

    cur1 = n > 0 ? head1 : head2; //cur1 指向长度较长的链表的头结点
    cur2 = cur1 == head1 ? head2 : head1; // cur2 指向长度较短的链表的头结点

    n = abs(n);

    while (n-- != 0) { //较长链表先移动n步
        cur1 = cur1->next;
    }

    while (cur1 != cur2) { //找到两个链表相交的第一个节点
        cur1 = cur1->next;
        cur2 = cur2->next;
    }

    return cur1;
}


Node *bothLoop(Node *head1, Node *loop1, Node *head2, Node *loop2) {
    Node *cur1 = nullptr;
    Node *cur2 = nullptr;
    //两个链表的入环节点是同一个,则入环节点看做终止节点，就是找两个无环链表的第一个相交节点
    if (loop1 == loop2) { //情况②
        cur1 = head1;
        cur2 = head2;
        int n = 0;
        while (cur1 != loop1) {
            n++;
            cur1 = cur1->next;
        }

        while (cur2 != loop2) {
            n--;
            cur2 = cur2->next;
        }

        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;

        n = abs(n);
        while (n-- != 0) {
            cur1 = cur1->next;
        }

        while (cur1 != cur2) {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }

        return cur1;
    } else {
        cur1 = loop1->next;
        while (cur1 != loop1) {
            if (cur1 == loop2) return loop1; //情况③ : 两个链表的入环节点不是同一个
            cur1 = cur1->next;
        }
        return nullptr; // 情况① ：两个链表各自有环，不相交
    }
}

Node *getIntersectNode(Node *head1, Node *head2) {
    if (head1 == nullptr || head2 == nullptr) return nullptr;

    Node *loop1 = getLoopNode(head1); //获取链表1的入环节点
    Node *loop2 = getLoopNode(head2); //获取链表2的入环节点
    if (loop1 == nullptr && loop2 == nullptr) { //如果两个链表都是无环的
        return noLoop(head1, head2);
    }
    if (loop1 != nullptr && loop2 != nullptr) { //两个链表都有环
        return bothLoop(head1, loop1, head2, loop2);
    }

    return nullptr;
}


int main() {

    // 1->2->3->4->5->6->7->null
	Node *head1 = new Node(1);
    head1->next = new Node(2);
    head1->next->next = new Node(3);
    head1->next->next->next = new Node(4);
    head1->next->next->next->next = new Node(5);
    head1->next->next->next->next->next = new Node(6);
    head1->next->next->next->next->next->next = new Node(7);


    // 0->9->8->6->7->null
    Node *head2 = new Node(0);
    head2->next = new Node(9);
    head2->next->next = new Node(8);
    head2->next->next->next = head1->next->next->next->next->next; // 8->6
    cout << getIntersectNode(head1, head2)->value << endl; // 6，两个无环链表相交

    // 1->2->3->4->5->6->7->4...
    head1 = new Node(1);
    head1->next = new Node(2);
    head1->next->next = new Node(3);
    head1->next->next->next = new Node(4);
    head1->next->next->next->next = new Node(5);
    head1->next->next->next->next->next = new Node(6);
    head1->next->next->next->next->next->next = new Node(7);
    head1->next->next->next->next->next->next = head1->next->next->next; // 7->4

    // 0->9->8->2...
    head2 = new Node(0);
    head2->next = new Node(9);
    head2->next->next = new Node(8);
    head2->next->next->next = head1->next; // 8->2
    cout << getIntersectNode(head1, head2)->value << endl; // 2，两个有环链表相交，且入环节点相同

    // 0->9->8->6->4->5->6..
    head2 = new Node(0);
    head2->next = new Node(9);
    head2->next->next = new Node(8);
    head2->next->next->next = head1->next->next->next->next->next; // 8->6
    cout << getIntersectNode(head1, head2)->value << endl; //4或者6，两个链表相交，且入环节点不同

    return 0;
}

Java 版

public class FindFirstIntersectNode {

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node getIntersectNode(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node loop1 = getLoopNode(head1);
		Node loop2 = getLoopNode(head2);
		if (loop1 == null && loop2 == null) {
			return noLoop(head1, head2);
		}
		if (loop1 != null && loop2 != null) {
			return bothLoop(head1, loop1, head2, loop2);
		}
		return null;
	}

	// 找到链表第一个入环节点，如果无环，返回null
	public static Node getLoopNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		// n1 慢  n2 快
		Node slow = head.next; // n1 -> slow
		Node fast = head.next.next; // n2 -> fast
		while (slow != fast) {
			if (fast.next == null || fast.next.next == null) {
				return null;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		// slow fast  相遇
		fast = head; // n2 -> walk again from head
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

	// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
	public static Node noLoop(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0;
		while (cur1.next != null) {
			n++;
			cur1 = cur1.next;
		}
		while (cur2.next != null) {
			n--;
			cur2 = cur2.next;
		}
		if (cur1 != cur2) {
			return null;
		}
		// n  :  链表1长度减去链表2长度的值
		cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
		cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
		n = Math.abs(n);
		while (n != 0) {
			n--;
			cur1 = cur1.next;
		}
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

	// 两个有环链表，返回第一个相交节点，如果不想交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		if (loop1 == loop2) {
			cur1 = head1;
			cur2 = head2;
			int n = 0;
			while (cur1 != loop1) {
				n++;
				cur1 = cur1.next;
			}
			while (cur2 != loop2) {
				n--;
				cur2 = cur2.next;
			}
			cur1 = n > 0 ? head1 : head2;
			cur2 = cur1 == head1 ? head2 : head1;
			n = Math.abs(n);
			while (n != 0) {
				n--;
				cur1 = cur1.next;
			}
			while (cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
			return cur1;
		} else {
			cur1 = loop1.next;
			while (cur1 != loop1) {
				if (cur1 == loop2) {
					return loop1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}

	public static void main(String[] args) {
		// 1->2->3->4->5->6->7->null
		Node head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(6);
		head1.next.next.next.next.next.next = new Node(7);

		// 0->9->8->6->7->null
		Node head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next.next.next.next.next; // 8->6
		System.out.println(getIntersectNode(head1, head2).value);

		// 1->2->3->4->5->6->7->4...
		head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		head1.next.next.next.next.next = new Node(6);
		head1.next.next.next.next.next.next = new Node(7);
		head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

		// 0->9->8->2...
		head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next; // 8->2
		System.out.println(getIntersectNode(head1, head2).value);

		// 0->9->8->6->4->5->6..
		head2 = new Node(0);
		head2.next = new Node(9);
		head2.next.next = new Node(8);
		head2.next.next.next = head1.next.next.next.next.next; // 8->6
		System.out.println(getIntersectNode(head1, head2).value);

	}
}

4、小结

判断一个链表是否有环

使用快慢指针，快指针一次走两步，慢指针一次走一步，若两个指针相遇，则表示有环。
如何找到有环链表的入环节点

当快慢指针相遇后，其中一个指针依然在当前位置，另一个指针指向链表头，然后两个指针同时往前以每次一步的节奏移动，再次相遇的位置就是链表的入环节点。
判断两个链表是否相交

遍历两个链表，记录下各自的尾结点，如果两个尾结点相等，则表示两个链表相交，否则不相交。
找到两个相交链表的第一个相交节点

在遍历链表的时候记录两个链表各自的长度len1 和 len2，指向较长的链表的指针先向前移动 |len1 - len2| 步，然后两个指针开始同步向前以每次一步的速度移动，两个指针相遇的位置就是第一个相交节点。

关于找到两个链表相交的第一个相交节点，可参考【Leetcode】160.相交链表，更加简便。