问题是写出能求出这条链表是否相交和找出第一个相交节点的函数,但是首先创建一条相交链表才能
或者怎么传进来一条链表?
要创建一条相交链表,可以先创建两条单独的链表,然后将它们的尾节点相连,形成一条相交链表。以下是一个示例代码:
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class IntersectionLinkedList {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 先找到两条链表的尾节点
ListNode tailA = headA;
while (tailA != null && tailA.next != null) {
tailA = tailA.next;
}
ListNode tailB = headB;
while (tailB != null && tailB.next != null) {
tailB = tailB.next;
}
// 如果两条链表的尾节点不同,说明不相交,返回null
if (tailA != tailB) {
return null;
}
// 将两条链表相连,形成一条相交链表
tailA.next = headB;
// 找到相交节点
ListNode intersectionNode = getIntersection(headA);
// 恢复链表
tailA.next = null;
return intersectionNode;
}
private ListNode getIntersection(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}
该代码中的 ListNode
类表示链表节点,包含一个整数值和一个指向下一个节点的指针。 IntersectionLinkedList
类包含一个 getIntersectionNode
方法,用于判断两条链表是否相交,并返回第一个相交节点。该方法先找到两条链表的尾节点,如果不同则说明不相交,直接返回 null
。如果相同,则将两条链表相连形成一条相交链表,然后调用另一个方法 getIntersection
来找到相交节点。该方法使用快慢指针法,先让快指针走两步,慢指针走一步,直到它们相遇,然后从头开始遍历链表,直到快指针和慢指针相遇,此时的节点就是相交节点。
创建链表可以定义一个方法,例如:
public ListNode createLinkedList(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
ListNode head = new ListNode(arr[0]);
ListNode tail = head;
for (int i = 1; i < arr.length; i++) {
ListNode node = new ListNode(arr[i]);
tail.next = node;
tail = node;
}
return head;
}
该方法接受一个整型数组,返回一个链表的头节点。例如,要创建一个值为 1 -> 2 -> 3 的链表,可以这样调用:
int[] arr = {1, 2, 3};
ListNode head = createLinkedList(arr);