Q37：两个链表的第一个公共结点

publicclass Q37两个链表的第一个公共结点 { /** * 题目：两个链表的第一个公共结点 * 题目说明：输入两个链表（从数据结构得出是单链表），找出它们的第一个公共结点。（公共结点说明数据域部分和指针域部分相同，因此在公共结点后的所有元素都重合，类似于字母“Y”的样式） * 解题思路（1）：使用蛮力搜索法，遍历链表1的每个元素，每遍历一个元素就遍历链表2每个结点。如果在第二个链表上有一个结点和第一个链表的结点一样，则就是我们要找的公共结点。 * 解题思路（2）：分别把两个链表放入两个栈中Stack1和Stack2中，这两个从栈顶开始遍历比较元素，直到找出两个栈最后一个相同的结点就是链表的第一个公共结点。 * 解题思路（3）：首先分别遍历两个链表，得出那个链表比较长，长的比短的多几个结点（假设多k个结点）。第二次遍历链表时，长的链表先遍历k个结点，接着同时遍历两个链表，找到第一个相同的结点就是它们的第一个公共结点。 */ publicstatic void main(String[] args) { ListNode head1=new ListNode(); ListNode second1=new ListNode(); ListNode third1=new ListNode(); ListNode forth1=new ListNode(); ListNode fifth1=new ListNode(); ListNode head2=new ListNode(); ListNode second2=new ListNode(); ListNode third2=new ListNode(); ListNode forth2=new ListNode(); head1.nextNode=second1; second1.nextNode=third1; third1.nextNode=forth1; forth1.nextNode=fifth1; head2.nextNode=second2; second2.nextNode=forth1; third2.nextNode=fifth1; head1.data=1; second1.data=2; third1.data=3; forth1.data=6; fifth1.data=7; head2.data=4; second2.data=5; third2.data=6; forth2.data=7; Q37两个链表的第一个公共结点 test=new Q37两个链表的第一个公共结点 (); System.out.println(test.theFirstCommonNode(head1,head2).data); } //解题思路（3）的代码如下 public ListNode theFirstCommonNode(ListNode head1, ListNode head2){ int length1 = getListLength(head1); int length2 = getListLength(head2); ListNode longListNode = null;//存放较长的链表 ListNode shortListNode = null;//存放较短的链表 int dif = 0; if(length1 > length2){ longListNode = head1; shortListNode = head2; dif = length1 - length2; }else{//(length1 < length2) longListNode = head2; shortListNode = head1; dif = length2 - length1; } for(int i = 0 ; i < dif; i++){//目的是将长的链表多的结点数遍历完，使得两个链表一样长 longListNode = longListNode.nextNode; } while(longListNode !=null && shortListNode != null && longListNode != shortListNode){ longListNode = longListNode.nextNode; shortListNode = shortListNode.nextNode; } return longListNode; } //遍历链表，获取链表的长度 publicint getListLength(ListNodeheadListNode){ int listLen = 0; //判断链表的合法性 if(headListNode ==null){ return listLen; } ListNode point = headListNode; while(point !=null){ point = point.nextNode; listLen ++; } return listLen; } }