链表相交_牛客题霸

给定两个无环单链表，它们可能在某一节点开始共享后缀，若存在第一个共享节点，则称为交点。请实现函数 getIntersectionNode，用于计算两个无环单链表交点节点，如果交点不存在则直接返回空。

输入描述:

函数参数由两个参数构成：链表 ：表示链表  的链表头，长度为 3\times10^4\right)" ；链表 ：表示链表  的链表头，长度为 3\times10^4\right)" ；

输出描述:

函数的返回值：返回两个无环单链表交点节点，如果交点不存在则直接返回空。

示例1

输入

输出

说明






相交节点的值为 5 。
从各自的表头开始算起，链表 A 为 [3,6,5,1,4]，链表 B 为 [1,1,4,5,1,4]。

加载中...

import java.util.*;

public class Main {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 在这里补充代码
        return null;
    }

//你不需要关心主函数的内容！
    public static void main(String[] args) {
        Main solution = new Main();
        Scanner scanner = new Scanner(System.in);
        
        // 读入数据
        int lenA = scanner.nextInt();
        int lenB = scanner.nextInt();
        int commonLen = scanner.nextInt();
        
        // 构建链表
        ArrayList<ListNode> nodesA = new ArrayList<>();
        ArrayList<ListNode> nodesB = new ArrayList<>();
        ArrayList<ListNode> nodesCommon = new ArrayList<>();
        
        // 读入并创建链表A的独立部分
        for (int i = 0; i < lenA - commonLen; i++) {
            int val = scanner.nextInt();
            nodesA.add(new ListNode(val));
            if (i > 0) nodesA.get(i-1).next = nodesA.get(i);
        }
        
        // 读入并创建链表B的独立部分
        for (int i = 0; i < lenB - commonLen; i++) {
            int val = scanner.nextInt();
            nodesB.add(new ListNode(val));
            if (i > 0) nodesB.get(i-1).next = nodesB.get(i);
        }
        
        // 读入并创建公共部分
        for (int i = 0; i < commonLen; i++) {
            int val = scanner.nextInt();
            nodesCommon.add(new ListNode(val));
            if (i > 0) nodesCommon.get(i-1).next = nodesCommon.get(i);
        }
        
        // 连接链表
        ListNode headA = null;
        ListNode headB = null;
        
        if (lenA - commonLen > 0) {
            headA = nodesA.get(0);
            if (commonLen > 0) nodesA.get(nodesA.size()-1).next = nodesCommon.get(0);
        } else if (commonLen > 0) {
            headA = nodesCommon.get(0);
        }
        
        if (lenB - commonLen > 0) {
            headB = nodesB.get(0);
            if (commonLen > 0) nodesB.get(nodesB.size()-1).next = nodesCommon.get(0);
        } else if (commonLen > 0) {
            headB = nodesCommon.get(0);
        }
        
        // 调用函数获取结果
        ListNode result = solution.getIntersectionNode(headA, headB);
        
        // 输出结果
        if (result == null) {
            System.out.println("null");
        } else {
            System.out.println(result.val);
        }
        
        scanner.close();
    }
}

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    // 在这里补充代码
}

//你不需要修改主函数内的代码！
int main() {
    // 读入数据
    int lenA, lenB, commonLen;
    cin >> lenA >> lenB >> commonLen;
    
    // 构建链表
    vector<ListNode*> nodesA(lenA - commonLen);
    vector<ListNode*> nodesB(lenB - commonLen);
    vector<ListNode*> nodesCommon(commonLen);
    
    // 读入并创建链表A的独立部分
    for (int i = 0; i < lenA - commonLen; i++) {
        int val;
        cin >> val;
        nodesA[i] = new ListNode(val);
        if (i > 0) nodesA[i-1]->next = nodesA[i];
    }
    
    // 读入并创建链表B的独立部分
    for (int i = 0; i < lenB - commonLen; i++) {
        int val;
        cin >> val;
        nodesB[i] = new ListNode(val);
        if (i > 0) nodesB[i-1]->next = nodesB[i];
    }
    
    // 读入并创建公共部分
    for (int i = 0; i < commonLen; i++) {
        int val;
        cin >> val;
        nodesCommon[i] = new ListNode(val);
        if (i > 0) nodesCommon[i-1]->next = nodesCommon[i];
    }
    
    // 连接链表
    ListNode* headA = nullptr;
    ListNode* headB = nullptr;
    
    if (lenA - commonLen > 0) {
        headA = nodesA[0];
        if (commonLen > 0) nodesA.back()->next = nodesCommon[0];
    } else if (commonLen > 0) {
        headA = nodesCommon[0];
    }
    
    if (lenB - commonLen > 0) {
        headB = nodesB[0];
        if (commonLen > 0) nodesB.back()->next = nodesCommon[0];
    } else if (commonLen > 0) {
        headB = nodesCommon[0];
    }
    
    // 调用函数获取结果
    ListNode* result = getIntersectionNode(headA, headB);
    
    // 输出结果
    if (result == nullptr) {
        cout << "null" << endl;
    } else {
        cout << result->val << endl;
    }
    
    // 清理内存
    for (auto node : nodesA) delete node;
    for (auto node : nodesB) delete node;
    for (auto node : nodesCommon) delete node;
    
    return 0;
}

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

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 在这里补充代码
    pass

# 你不需要关心主函数内容！
def main():
    # 读入数据
    lenA, lenB, commonLen = map(int, input().split())

# 读入链表A的独立部分
    valuesA = list(map(int, input().split()))
    # 读入链表B的独立部分
    valuesB = list(map(int, input().split()))
    # 读入公共部分
    valuesCommon = list(map(int, input().split()))
    nodesCommon=[]
    if(commonLen==0):
        nodesCommon=[]
    else:
        nodesCommon = [ListNode(x) for x in valuesCommon]

# 构建链表
    nodesA = [ListNode(x) for x in valuesA]
    nodesB = [ListNode(x) for x in valuesB]

# 连接链表A的独立部分
    for i in range(len(nodesA) - 1):
        nodesA[i].next = nodesA[i + 1]

# 连接链表B的独立部分
    for i in range(len(nodesB) - 1):
        nodesB[i].next = nodesB[i + 1]

# 连接公共部分
    for i in range(len(nodesCommon) - 1):
        nodesCommon[i].next = nodesCommon[i + 1]

# 设置头节点并连接公共部分
    headA = None
    headB = None

if len(nodesA) > 0:
        headA = nodesA[0]
        if len(nodesCommon) > 0:
            nodesA[-1].next = nodesCommon[0]
    elif len(nodesCommon) > 0:
        headA = nodesCommon[0]

if len(nodesB) > 0:
        headB = nodesB[0]
        if len(nodesCommon) > 0:
            nodesB[-1].next = nodesCommon[0]
    elif len(nodesCommon) > 0:
        headB = nodesCommon[0]

# 调用函数获取结果
    result = getIntersectionNode(headA, headB)

# 输出结果
    if result is None:
        print("null")
    else:
        print(result.val)

if __name__ == "__main__":
    main()