Popular Algorithm 100: 160. Intersection of Two Linked Lists

Popular Algorithm 100: 160. Intersection of Two Linked Lists

Overview

Given the head nodes of two singly linked lists, headA and headB, find and return the starting node where the two linked lists intersect. If there is no intersection, return null.

The two linked lists intersect at node c1:

The problem guarantees that there are no cycles in the entire linked structure.

Note that after the function returns the result, the linked lists must maintain their original structure.

Solution

Case 1: The two linked lists intersect

The lengths of linked lists headA and headB are m and n, respectively. Let x be the number of nodes in the non-intersecting part of headA, y be the number of nodes in the non-intersecting part of headB, and z be the number of nodes in the intersecting part. Then we have m = x + z and n = y + z.

If x = y, then both pointers will reach the intersection node at the same time, and we return the intersection node;

If x ≠ y, then pointer pA will traverse the entire linked list headA, and pointer pB will traverse the entire linked list headB. The two pointers will not reach the tail node of the linked lists at the same time. Then, pointer pA moves to the head node of linked list headB, and pointer pB moves to the head node of linked list headA. The two pointers continue to move, and after pointer pA has moved m times and pointer pB has moved n times, both pointers will reach the intersection node, which is also the first node that both pointers point to at the same time. We return the intersection node.

Case 2: The two linked lists do not intersect

The lengths of linked lists headA and headB are x and y, respectively. Consider when x ≠ y, how the two pointers will move:

If x = y, then both pointers will reach the tail nodes of the two linked lists at the same time and will both become null, at which point we return null;

If x ≠ y, since there are no common nodes between the two linked lists, the two pointers will not reach the tail nodes of the two linked lists at the same time. Therefore, both pointers will traverse the two linked lists, and after pointer pA has moved x times and pointer pB has moved y times, both pointers will become null, at which point we return null.

Let’s look at a step-by-step illustration (source: leetcode: Lingcha Mountain Ai Mansion):

Below is the complete test code:

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, PartialEq, Eq)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<rc<refcell>>,
}

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

pub fn get_intersection_node(
    head_a: Option<rc<refcell>>,
    head_b: Option<rc<refcell>>,
) -> Option<rc<refcell>> {
    let mut p = head_a.clone();
    let mut q = head_b.clone();

    while p != q {
        p = match p {
            Some(node) => node.borrow().next.clone(),
            None => head_b.clone(),
        };
        q = match q {
            Some(node) => node.borrow().next.clone(),
            None => head_a.clone(),
        };
    }

    p
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_no_intersection() {
        let node1 = Rc::new(RefCell::new(ListNode::new(1)));
        let node2 = Rc::new(RefCell::new(ListNode::new(2)));
        let node3 = Rc::new(RefCell::new(ListNode::new(3)));

        node1.borrow_mut().next = Some(Rc::clone(&node2));
        node2.borrow_mut().next = Some(Rc::clone(&node3));

        let node4 = Rc::new(RefCell::new(ListNode::new(4)));
        let node5 = Rc::new(RefCell::new(ListNode::new(5)));

        node4.borrow_mut().next = Some(Rc::clone(&node5));

        assert_eq!(get_intersection_node(Some(node1), Some(node4)), None);
    }

    #[test]
    fn test_with_intersection() {
        let node1 = Rc::new(RefCell::new(ListNode::new(1)));
        let node2 = Rc::new(RefCell::new(ListNode::new(2)));
        let node3 = Rc::new(RefCell::new(ListNode::new(3)));
        let node4 = Rc::new(RefCell::new(ListNode::new(4)));

        node1.borrow_mut().next = Some(Rc::clone(&node2));
        node2.borrow_mut().next = Some(Rc::clone(&node3));
        node3.borrow_mut().next = Some(Rc::clone(&node4));

        let node5 = Rc::new(RefCell::new(ListNode::new(5)));
        node5.borrow_mut().next = Some(Rc::clone(&node3));

        assert_eq!(
            get_intersection_node(Some(node1), Some(node5)),
            Some(Rc::clone(&node3))
        );
    }

    #[test]
    fn test_one_empty_list() {
        let node1 = Rc::new(RefCell::new(ListNode::new(1)));
        let node2 = Rc::new(RefCell::new(ListNode::new(2)));

        node1.borrow_mut().next = Some(Rc::clone(&node2));

        assert_eq!(get_intersection_node(Some(node1), None), None);
    }
}

fn main () {
    print!("intersection link!");
}       </rc<refcell</rc<refcell</rc<refcell</rc<refcell