相交链表

• 题目要求
• 解题思路
• Golang 版本
• C++版本
• Python 版本
• Java 版本
• Rust 版本
• 总结

题目要求

编写一个函数，该函数接受两个单链表的头节点 headA 和 headB 作为输入参数。任务是找出这两个单链表相交的第一个节点。如果两个链表没有交点，则函数应返回 null。链表的相交是指从某个节点开始，它们共享所有后续节点，即从这一点开始，两个链表合并为一个。

解题思路

要解决这个问题，我们可以采用以下步骤：

1. 双指针法：

   • 初始化两个指针，分别指向两个链表的头节点 headA 和 headB。
   • 同时遍历两个链表，当一个指针到达链表末尾时，将其重定向到另一个链表的头节点继续遍历。
   • 如果两个链表相交，那么这两个指针最终会在相交节点处相遇。这是因为重定向指针后，两个指针到达相交节点的路径长度相同。
   • 如果两个链表不相交，那么这两个指针最终都会同时到达各自链表的末尾（null），这时返回 null。

2. 长度差法：

   • 首先遍历两个链表，得到它们的长度和长度差。
   • 然后将较长链表的指针向前移动长度差个节点。
   • 接着同时遍历两个链表，比较当前指针指向的节点是否相同。
   • 如果找到相同的节点，则该节点为相交的起始节点。
   • 如果直到链表末尾都没有找到相同的节点，则返回 null。

3. 哈希表法：

   • 遍历第一个链表，将所有节点存储在哈希表中。
   • 然后遍历第二个链表，检查每个节点是否已存在于哈希表中。
   • 如果存在，则该节点为两个链表相交的起始节点。
   • 如果遍历完第二个链表都没有找到存在于哈希表中的节点，则返回 null。

在实际应用中，双指针法因为其空间复杂度较低（O(1)）和简洁性通常是首选方法。长度差法和哈希表法的空间复杂度分别为 O(1)和 O(N)，其中 N 是链表节点的数量。

Golang 版本

package main

import (
	"fmt"
)

// ListNode is a definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

// getIntersectionNode finds the node at which the intersection of two singly linked lists begins.
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}

	// Create two pointers for each list.
	pA := headA
	pB := headB

	// Continue until they either meet or end.
	for pA != pB {
		// If you reached the end of one list, go to the beginning of the other one.
		// You only switch once for each pointer.
		if pA == nil {
			pA = headB
		} else {
			pA = pA.Next
		}

		if pB == nil {
			pB = headA
		} else {
			pB = pB.Next
		}
	}

	// If pA and pB meet, pA/pB is the intersection node.
	return pA
}

func main() {
	// Example usage:
	// The linked lists setup and intersection node creation should be here.
	// This is just a function usage example assuming 'headA' and 'headB' are already defined and intersect.
	intersectionNode := getIntersectionNode(headA, headB)
	fmt.Println("Intersection node:", intersectionNode)
}

请注意，这段代码假设headA和headB是已经定义好的变量，并且它们代表的链表可能在某个节点相交。在实际使用中，你需要根据具体情况来创建这些链表和它们的交点。这段代码只展示了getIntersectionNode函数的实现和如何调用它。

C++版本

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) return NULL;

        ListNode *pA = headA;
        ListNode *pB = headB;

        // After switching, both pointers will travel the same distance
        while (pA != pB) {
            // Switch to the head of the other list upon reaching the end
            pA = pA == NULL ? headB : pA->next;
            pB = pB == NULL ? headA : pB->next;
        }

        // If pA and pB meet, pA/pB is the intersection node, otherwise NULL
        return pA;
    }
};

int main() {
    // Example usage:
    // The linked lists setup and intersection node creation should be here.
    // This is just a function usage example assuming 'headA' and 'headB' are already defined and intersect.
    Solution solution;
    ListNode *intersectionNode = solution.getIntersectionNode(headA, headB);
    std::cout << "Intersection node: " << (intersectionNode ? intersectionNode->val : -1) << std::endl;
    return 0;
}

这段代码提供了一个Solution类，其中包含了getIntersectionNode函数的实现。这个函数使用了双指针法来找出两个链表的交点。在main函数中，你需要根据实际情况来创建链表和它们的交点，然后创建Solution类的实例并调用getIntersectionNode函数。这里的代码只是一个调用示例，假设headA和headB是已经定义好的变量，并且它们代表的链表可能在某个节点相交。

Python 版本

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None

        # Set two pointers to each head
        pA, pB = headA, headB

        # Iterate through the lists
        while pA is not pB:
            # If either pointer hits the end, switch head and continue the second traversal,
            # if not intersect, the second traversal will hit the end at the same time and return None
            pA = pB if pA is None else pA.next
            pB = pA if pB is None else pB.next

        # If pA and pB meet, pA/pB is the intersection node, otherwise None
        return pA

# Example usage:
# Assuming that 'headA' and 'headB' are the heads of the two linked lists which are already defined.
# solution = Solution()
# intersection_node = solution.getIntersectionNode(headA, headB)
# print(intersection_node.val if intersection_node else 'No intersection')

这段代码定义了一个ListNode类用于表示链表节点，以及一个Solution类，其中包含了getIntersectionNode方法。这个方法使用了双指针技巧来找出两个链表的交点。在实际使用中，你需要创建两个链表的实例并且可能需要创建它们的交点，然后创建Solution类的实例并调用getIntersectionNode方法。这里的代码只是一个调用示例，假设headA和headB是已经定义好的变量，并且它们代表的链表可能在某个节点相交。

Java 版本

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode pA = headA;
        ListNode pB = headB;

        // After both pointers have traversed through their respective lists,
        // they will have covered the same distance when they meet at the intersection point.
        while (pA != pB) {
            // If either pointer reaches the end, switch to the head of the other list.
            // If there is no intersection, both will eventually become null.
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        // If pA and pB meet, pA/pB is the intersection node, otherwise null.
        return pA;
    }
}

// Example usage:
// Assuming that 'headA' and 'headB' are the heads of the two linked lists which are already defined.
// Solution solution = new Solution();
// ListNode intersectionNode = solution.getIntersectionNode(headA, headB);
// System.out.println(intersectionNode != null ? intersectionNode.val : "No intersection");

这段代码定义了一个ListNode类用于表示链表节点，以及一个Solution类，其中包含了getIntersectionNode方法。这个方法使用了双指针技巧来找出两个链表的交点。在实际使用中，你需要创建两个链表的实例并且可能需要创建它们的交点，然后创建Solution类的实例并调用getIntersectionNode方法。这里的代码只是一个调用示例，假设headA和headB是已经定义好的变量，并且它们代表的链表可能在某个节点相交。

Rust 版本

#![allow(unused)]
fn main() {
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

pub struct Solution;

impl Solution {
    pub fn get_intersection_node(
        head_a: Option<Box<ListNode>>,
        head_b: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        // Convert the Option<Box<ListNode>> to raw pointers for comparison
        let mut p_a: *const ListNode = head_a.as_ref().map_or(std::ptr::null(), |n| &**n);
        let mut p_b: *const ListNode = head_b.as_ref().map_or(std::ptr::null(), |n| &**n);

        // We'll need to keep the original heads to reset the pointers after the first pass
        let mut head_a = head_a;
        let mut head_b = head_b;

        // If either pointer is null (i.e., the list is empty), there's no intersection
        if p_a.is_null() || p_b.is_null() {
            return None;
        }

        while p_a != p_b {
            // Move to the next node, or switch to the other list's head after reaching the end
            p_a = if let Some(node) = unsafe { p_a.as_ref() } {
                node.next.as_ref().map_or(std::ptr::null(), |n| &**n)
            } else {
                head_b.as_ref().map_or(std::ptr::null(), |n| &**n)
            };

            p_b = if let Some(node) = unsafe { p_b.as_ref() } {
                node.next.as_ref().map_or(std::ptr::null(), |n| &**n)
            } else {
                head_a.as_ref().map_or(std::ptr::null(), |n| &**n)
            };
        }

        // Once the pointers meet, return the intersection node as Option<Box<ListNode>>
        unsafe { p_a.as_ref() }.map(|node| Box::new(ListNode::new(node.val)))
    }
}

// Example usage:
// Assuming that 'head_a' and 'head_b' are the heads of the two linked lists which are already defined.
// let intersection_node = Solution::get_intersection_node(head_a, head_b);
// println!("{:?}", intersection_node);
}

这段代码定义了一个ListNode结构体用于表示链表节点，以及一个Solution结构体，其中包含了get_intersection_node方法。这个方法使用了双指针技巧来找出两个链表的交点。在实际使用中，你需要创建两个链表的实例并且可能需要创建它们的交点，然后调用Solution::get_intersection_node方法。这里的代码只是一个调用示例，假设head_a和head_b是已经定义好的变量，并且它们代表的链表可能在某个节点相交。

请注意，Rust 的安全性原则通常不推荐使用裸指针和unsafe代码块。然而，在这个特定的例子中，为了模拟其他语言中的指针比较操作，我们不得不使用它们。在实际的 Rust 生产代码中，应该尽量避免这样的做法，而是寻找更安全的替代方案。

总结

上面给出了使用双指针法来解决两个单链表相交问题的代码示例。这种方法是一种高效的解决方案，不需要额外的空间，且时间复杂度为 O(m+n)，其中 m 和 n 分别是两个链表的长度。

双指针法的基本思路是同时遍历两个链表，当一个指针到达链表末尾时，将其重定向到另一个链表的头节点继续遍历。如果两个链表相交，那么这两个指针最终会在相交节点处相遇。如果两个链表不相交，那么这两个指针最终都会同时到达各自链表的末尾（null）。

除了双指针法，还介绍了长度差法和哈希表法。长度差法首先遍历两个链表，得到它们的长度和长度差，然后将较长链表的指针向前移动长度差个节点，接着同时遍历两个链表，比较当前指针指向的节点是否相同。哈希表法则是遍历第一个链表，将所有节点存储在哈希表中，然后遍历第二个链表，检查每个节点是否已存在于哈希表中。

这些方法都可以有效地找出两个单链表的相交节点，选择合适的方法取决于具体的应用场景和需求。