leetcode160：相交链表

题目链接

leetcode

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        if (head->next != nullptr) cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    哈希集合

    遍历链表 headA，并将链表 headA 中的每个结点加入哈希集合中。
    遍历链表 headB，对于遍历到的每个结点，判断该结点是否在哈希集合中：
        如果当前结点不在哈希集合中，则继续遍历下一个结点；
        如果当前结点在哈希集合中，则后面的结点都在哈希集合中。
    因此，在链表 headB 中遍历到的第一个在哈希集合中的结点就是两个链表相交的结点。

    时间复杂度：O(m + n)
        其中 m 和 n 是分别是链表 headA 和 headB 的长度。
        遍历两个链表各一次。
    空间复杂度：O(m)
        其中 m 是链表 headA 的长度。
        使用哈希集合存储链表 headA 中的全部结点。
*/
class Solution_0 {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;

        ListNode* temp = headA;
        while (temp != nullptr) {
            visited.insert(temp);
            temp = temp->next;
        }

        temp = headB;
        while (temp != nullptr) {
            if (visited.count(temp)) {
                return temp;
            }
            temp = temp->next;
        }

        return nullptr;
    }
};

/*
    双指针，指针扫描

    1.两个指针分别从两个链表头部开始扫描，每次分别走一步；
    2.如果指针走到 null，则从另一个链表头部开始走；
    3.当两个指针相同时，
        如果指针不是 null，那么指针位置就是相遇点；
        如果指针是 null，那么两个链表不相交；

    时间复杂度：O(m + n)
        其中 m 和 n 是分别是链表 headA 和 headB 的长度。
        两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
    空间复杂度：O(1)
        只使用了固定的两个指针。
*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;

        ListNode *p1 = headA, *p2 = headB;
        while (p1 != p2) {
            // p1 = (p1 == nullptr ? headB : p1->next);
            // p2 = (p2 == nullptr ? headA : p2->next);
            p1 = p1 == nullptr ? headB : p1->next;
            p2 = p2 == nullptr ? headA : p2->next;
        }

        return p1;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> listA_nums = {4, 1, 8, 4, 5};
    vector<int> listB_nums = {5, 6, 1, 8, 4, 5};

    // 创建链表
    ListNode* headA = createList(listA_nums);
    ListNode* headB = createList(listB_nums);
    printList(headA);
    printList(headB);

    // 设置相交结点
    ListNode* inserted_A = headA->next->next;
    ListNode* inserted_B_prev = headB->next->next;
    ListNode* inserted_B = inserted_B_prev->next;
    inserted_B_prev->next = inserted_A;
    inserted_B->next = nullptr;
    delete inserted_B;
    printList(headA);
    printList(headB);

    // 打印结果
    cout << "Intersection Node: ";
    printList(solution.getIntersectionNode(headA, headB));

    // 释放内存
    deleteList(headA);
    deleteList(headB);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    基本思路：
        创建了一个哈希表 visited 来存储已经访问过的节点。
        在遍历两个链表时，将当前节点添加到哈希表中。
        若遍历过程中找到在哈希表中的节点，则说明找到了交点；
        否则，直接返回该节点。

    时间复杂度：O(m + n)
        其中 m 和 n 分别是两个链表的长度。
        遍历两个链表各一次。
    空间复杂度：O(m)
        其中 m 是链表 headA 的长度。
        使用哈希集合存储链表 headA 中的全部节点。
*/
// 找到两个链表的交点
func getIntersectionNode_0(headA, headB *ListNode) *ListNode {
    visited := make(map[*ListNode]bool)
    
    for node := headA; node != nil; node = node.Next {
        visited[node] = true
    }
    for node := headB; node != nil; node = node.Next {
        if visited[node] {
            return node
        }
    }

    return nil
}

/*

    基本思路：
        使用两个指针同时遍历两个链表。
        当指针 pA 到达链表末尾时，将其指向链表 headB 的头节点；
        当指针 pB 到达链表末尾时，将其指向链表 headA 的头节点。
        这样，两个指针最终会在交点处相遇，或者同时到达链表末尾（没有交点）。

    时间复杂度：O(m + n)
        其中 m 和 n 分别是两个链表的长度。
        两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
    空间复杂度：O(1)
        只使用了固定的两个指针。
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }

    pa, pb := headA, headB
    for pa != pb {
        // 若指针 pa 到达链表末尾，则将其指向链表 headB 的头节点
        if pa == nil {
            pa = headB
        } else {
            pa = pa.Next
        }

        // 若指针 pB 到达链表末尾，则将其指向链表 headA 的头节点
        if pb == nil {
            pb = headA
        } else {
            pb = pb.Next
        }
    }

    // 当两个指针相等时，返回交点节点
    return pa
}

func main() {
    // 测试用例
    testCases := []struct {
        expected []int  // 预期相交节点的后续值
        headA    []int  // 链表A的值（相交前部分）
        headB    []int  // 链表B的值（相交前部分）
    }{
        {
            expected: []int{8, 4, 5},
            headA:    []int{4, 1},
            headB:    []int{5, 6, 1},
        },
        {
            expected: []int{2, 4},
            headA:    []int{1, 9, 1},
            headB:    []int{3},
        },
        {
            expected: nil,
            headA:    []int{2, 6, 4},
            headB:    []int{1, 5},
        },
    }

    for i, tc := range testCases {
        var commonNode *ListNode
        if tc.expected != nil {
            commonNode = createLinkedList(tc.expected)
        }

        headA := createLinkedList(tc.headA)
        if headA != nil {
            current := headA
            for current.Next != nil {
                current = current.Next
            }
            current.Next = commonNode
        } else {
            headA = commonNode
        }

        headB := createLinkedList(tc.headB)
        if headB != nil {
            current := headB
            for current.Next != nil {
                current = current.Next
            }
            current.Next = commonNode
        } else {
            headB = commonNode
        }

        fmt.Printf("Test Case %d, Input: headA = %v, headB = %v\n", i+1, printLinkedList(headA), printLinkedList(headB))
        result := getIntersectionNode(headA, headB)
		resultStr := printLinkedList(result)
        expected := commonNode
        expectedStr := printLinkedList(expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}