代码来自闵老师”日撸 Java 三百行（31-40天）“，链接：https://blog.csdn.net/minfanphd/article/details/116975772
理解参考博文：https://blog.csdn.net/xiangxizhishi/article/details/79119532
对于十字（交叉）链表，个人感觉把出度，入度和矩阵里面的上下左右结合比较好理解。博文中将出度的下一个节点定义为right，将入度的下一个节点定义为down，和矩阵更贴切。十字链表有两个头链表，分别对应行的头和列的头；头链表没有数据，只是指向该行（列）的第一个元素，只有起始指针的意义。便于理解这里借用一下原博客的图：
package datastructure.graph;public class OrthogonalList {class OrthogonalNode {int row;int column;OrthogonalNode nextOut;OrthogonalNode nextIn;public OrthogonalNode(int paraRow, int paraColumn) {// TODO Auto-generated constructor stubrow = paraRow;column = paraColumn;nextOut = null;nextIn = null;}//The first constructor of OrthogonalNode}//of class OrthogonalNodeint numNodes;OrthogonalNode[] headers;public OrthogonalList(int[][] paraMatrix) {// TODO Auto-generated constructor stubnumNodes = paraMatrix.length;// Step 1、Initialize、The data in the headers are not meaningful.OrthogonalNode tempPreviouNode,tempNode;headers = new OrthogonalNode[numNodes];//Step 2、link to its out nodes.for (int i = 0; i < paraMatrix.length; i++) {headers[i] = new OrthogonalNode(i, -1);tempPreviouNode = headers[i];for (int j = 0; j < numNodes; j++) {if (paraMatrix[i][j] == 0) {continue;}//of if// Create a new node.tempNode = new OrthogonalNode(i, j);// link.tempPreviouNode.nextOut = tempNode;tempPreviouNode = tempNode;}//of for j}//of for i//Step 3、link to its in nodes、This step is harder.OrthogonalNode[] tempColumnNodes = new OrthogonalNode[numNodes];for (int i = 0; i < numNodes; i++) {tempColumnNodes[i] = headers[i]; //作用相当于tempPreviouNode}//of for ifor (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextOut;while (tempNode != null) {tempColumnNodes[tempNode.column].nextIn = tempNode;tempColumnNodes[tempNode.column] = tempNode;tempNode = tempNode.nextOut;}//of while}//of for i}//The first constructor of OrthogonalListpublic String toString() {String resultString = "Out arcs: ";OrthogonalNode tempNode;for (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextOut;while (tempNode != null) {resultString += " (" + tempNode.row + ", " + tempNode.column + ")";tempNode = tempNode.nextOut;}//of while}//of for iresultString += "rnIn arcs: ";for (int i = 0; i < numNodes; i++) {tempNode = headers[i].nextIn;while (tempNode != null) {resultString += " (" + tempNode.row + ", " + tempNode.column + ")";tempNode = tempNode.nextIn;}//of while//resultString += "rn";}//of for ireturn resultString;}//of toStringpublic static void main(String args[]) {int[][] tempMatrix = {{0, 1, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, 1, 1, 0}};OrthogonalList tempList = new OrthogonalList(tempMatrix);System.out.println("The data are:rn" + tempList);}//of main}//of class OrthogonalList
第三步连接入度节点的时候，是通过行来遍历节点，通过列来连接各个节点。其中tempNode遍历行，tempColumnNodes作用相当于第二步中的tempPreviouNode，用来连接节点。（理解起来确实有点儿头大，设计是相当巧妙的）