java 相交链表的实现示例

java 相交链表的实现示例

目录1.题目2.分析3.完整代码

1.题目

相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。相交链表

2.分析

相交链表是Y字型，next域相同。

定义两个引用pl和ps，

如果每个链表相交结点前长度相同，一步一步走，直到相同就找到了相交结点。如果长度不一样，首先要长链表先走差值步，然后再一人走一步直到相遇

长度不同：

长度相同：

首先求长度，先假设pl指向headA：

ListNode pl = headA;

ListNode ps = headB;

int lenA = 0;

int lenB = 0;

while (pl != null) {

lenA++;

pl = pl.next;

}

//pl==null;

pl = headA;

while (ps != null) {

lenB++;

ps = ps.next;

}

//ps==null;

ps = headB;

然后根据长度差值的正负判断谁长，将pl指向长的链表：

int len = lenA - lenB;//差值步

if (len < 0) {

pl = headB;

ps = headA;

len = lenB - lenA;

}

然后长的先走长度差值步，最后一人一步走：

//pl走差值len步

while (len != 0) {

pl = pl.next;

len--;

}

//同时走，直到相遇

while (pl != ps) {

pl = pl.next;

ps = ps.next;

}

return pl;

}

3.完整代码

//判断链表相交

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

if (headA == null || headB == null) {

return null;

}

ListNode pl = headA;

ListNode ps = headB;

int lenA = 0;

int lenB = 0;

while (pl != null) {

lenA++;

pl = pl.next;

}

//pl==null;

pl = headA;

while (ps != null) {

lenB++;

ps = ps.next;

}

//ps==null;

ps = headB;

int len = lenA - lenB;//差值步

if (len < 0) {

pl = headB;

ps = headA;

len = lenB - lenA;

}

//1、pl永远指向最长的链表 ps永远指向最短的链表 2、求到了差值len步

//pl走差值len步

while (len != 0) {

pl = pl.next;

len--;

}

//同时走，直到相遇

while (pl != ps) {

pl = pl.next;

ps = ps.next;

}

return pl;

}

测试：

public static void main(String[] args) {

MyLinkedList myLinkedList = new MyLinkedList();

myLinkedList.addLast(12);

myLinkedList.addLast(23);

myLinkedList.addLast(34);

myLinkedList.addLast(45);

System.out.println("myLinkedList：");

myLinkedList.display();

MyLinkedList myLinkedList1 = new MyLinkedList();

myLinkedList1.addLast(13);

myLinkedList1.addLast(22);

myLinkedList1.addLast(30);

System.out.println("myLinkedList1：");

myLinkedList1.display();

createCut(myLinkedList.head, myLinkedList1.head);

try {

ListNode ret = getIntersectionNode(myLinkedList.head, myLinkedList1.head);

myLinkedList.display2(ret);

} catch (NullPointerException e) {

e.printStackTrace();

System.out.println("没有相交结点！");

}

}

MyLinkedList myLinkedList = new MyLinkedList();

myLinkedList.addLast(12);

myLinkedList.addLast(23);

myLinkedList.addLast(34);

myLinkedList.addLast(56);

System.out.println("myLinkedList:");

myLinkedList.display();

MyLinkedList myLinkedList1 = new MyLinkedList();

myLinkedList1.addLast(12);

myLinkedList1.addLast(23);

myLinkedList1.addLast(30);

System.out.println("myLinkedList1:");

myLinkedList1.display();

//createCut(myLinkedList.head,myLinkedList1.head);

try {

ListNode ret = getIntersectionNode(myLinkedList.head, myLinkedList1.head);

SysteoMTOcICvm.out.println(ret.val);

}catch (NullPointerException e){

e.printStackTrace();

System.out.println("不存在相交结点！");

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。