【算法刷题】链表分割、链表的回文结构、相交链表

链表分割

题目来源：链表分割

题目描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

解题思路

可以通过遍历链表的方法，将小于给定值 x 的节点与大于等于 x 的节点分别连接在一起，从而重新排列链表。以下是实现这一功能的 Java 代码：

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public ListNode partition(ListNode pHead, int x) {// 创建两个新的链表，分别存放小于x和大于等于x的节点ListNode lessHead = new ListNode(0); // 虚拟头结点，用于存放小于x的节点ListNode greaterHead = new ListNode(0); // 虚拟头结点，用于存放大于等于x的节点ListNode less = lessHead; // 指针，指向小于x链表的尾部ListNode greater = greaterHead; // 指针，指向大于等于x链表的尾部ListNode current = pHead; // 当前遍历的节点// 遍历原链表while (current != null) {if (current.val < x) {less.next = current; // 将节点接到less链表上less = less.next; // 移动less指针} else {greater.next = current; // 将节点接到greater链表上greater = greater.next; // 移动greater指针}current = current.next; // 移动到下一个节点}// 连接两个链表less.next = greaterHead.next; // 将less链表和greater链表连接greater.next = null; // 避免形成环return lessHead.next; // 返回新链表的头指针
}

代码说明：

1. ListNode类：定义了链表节点，包含一个值 val 和一个指向下一个节点的指针 next。
2. partition方法：
   • 创建两个虚拟头节点 lessHead 和 greaterHead 用于分别存放小于 x 和大于等于 x 的节点。
   • 使用两个指针 less 和 greater 来构建两个新链表。
   • 遍历原链表，根据节点值的大小将节点连接到相应的新链表中。
   • 最后，将小于 x 的链表与大于等于 x 的链表连接，并返回新链表的头指针。

这个方法的时间复杂度为 O(n)，空间复杂度为 O(1)，因为我们只使用了 O(1) 的额外空间来存放指针。

链表的回文结构

题目来源：链表的回文结构

题目描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

解题思路

判断链表是否为回文结构的基本思路是使用快慢指针找到链表的中间节点，然后反转后半部分链表，再与前半部分进行比较。以下是使用 Java 实现该算法的代码：

算法步骤：

1. 使用快慢指针来找到链表的中间节点。
2. 反转后半部分链表。
3. 比较前半部分和反转后的后半部分。
4. 恢复链表的原状（可选）。
5. 返回比较结果。

Java 代码实现：

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true; // 空链表或只有一个节点的链表是回文}// 1. 使用快慢指针找到中间节点ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next; // 慢指针每次走一步fast = fast.next.next; // 快指针每次走两步}// 2. 反转后半部分ListNode prev = null;ListNode current = slow; // 现在的慢指针指向中间节点while (current != null) {ListNode nextTemp = current.next; // 暂存下一个节点current.next = prev; // 反转指向prev = current; // 移动prev指针current = nextTemp; // 移动current指针}// prev 现在指向反转后的后半部分的头// 3. 比较前半部分和后半部分ListNode l1 = head; // 前半部分ListNode l2 = prev; // 后半部分（已反转）while (l2 != null) {if (l1.val != l2.val) {return false; // 不相等则不是回文}l1 = l1.next; // 移动前半部分指针l2 = l2.next; // 移动后半部分指针}// 4. 恢复链表可以在这里进行（可选），但不影响结果return true; // 如果比较完都相等，则是回文}
}

代码说明：

1. ListNode类：定义链表节点，包含一个整数值 val 和一个指向下一个节点的指针 next。
2. isPalindrome方法：
   • 首先处理空链表和单节点链表的情况，直接返回 true。
   • 利用快慢指针的方法找到链表的中间节点。
   • 将链表的后半部分反转。
   • 比较前半部分和后半部分的节点值是否相同。
   • 返回结果 true 或 false。

时间复杂度与空间复杂度：

• 时间复杂度：O(n)，n 是链表的长度，因为我们对链表进行了三次遍历（找到中间节点、反转后半部分、比较前后部分）。
• 空间复杂度：O(1)，只使用了有限的额外空间来存储指针。

相交链表

题目来源：相交链表

题目描述

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

解题思路

方案一：

要找出两个单链表的相交节点，可以使用双指针的方法。这个方法的核心思想是通过同时遍历两个链表，来找出它们的交点。下面是解决这个问题的步骤及实现代码。

算法步骤：

1. 定义两个指针：指针 pA 从链表 A 的头开始，指针 pB 从链表 B 的头开始。
2. 遍历链表：两个指针同时移动：
   • 当 pA 到达链表 A 的尾部时，转到链表 B 的头部。
   • 当 pB 到达链表 B 的尾部时，转到链表 A 的头部。
3. 相遇判断：此过程保证了若两个链表相交，则两个指针最终会在交点相遇；否则，它们都会在结束时同时为 null，因此也能正确返回 null。

Java 代码实现：

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null; // 如果任一链表为空，则没有交点}ListNode pA = headA;ListNode pB = headB;// 当两个指针相遇时，即为交点，或同时为 null（结束遍历）while (pA != pB) {// 当到达链表尾部时，转到另一链表的头部pA = (pA == null) ? headB : pA.next;pB = (pB == null) ? headA : pB.next;}return pA; // 返回交点（可以是 null）}
}

代码说明：

1. ListNode类：定义了链表节点，包含一个整数值 val 和一个指向下一个节点的指针 next。
2. getIntersectionNode方法：
   • 首先检查链表是否为空。
   • 定义两个指针 pA 和 pB，分别从 headA 和 headB 开始。
   • 使用 while 循环遍历两个链表，直到两个指针相等。
   • 每个指针在到达链表的末尾时，都会转向另一个链表的头。这使得两个指针遍历的总长度相同，因此在交点处相遇。

时间复杂度与空间复杂度：

• 时间复杂度：O(n + m)，其中 n 和 m 分别是链表 A 和 B 的长度，因为每个指针在最坏情况下都需要遍历整个链表。
• 空间复杂度：O(1)，只使用了有限的额外指针，不需要额外的存储空间。

方案二：

除了使用双指针的方法，我们还可以使用哈希集合来找出两个链表的交点。这种方法涉及到将一个链表的所有节点存储在哈希集合中，然后遍历另一个链表，查看是否有节点存在于该集合中。

算法步骤：

1. 使用哈希集合：创建一个哈希集合来存储链表 A 中的所有节点。
2. 遍历链表 A：将链表 A 中的每个节点插入到哈希集合中。
3. 遍历链表 B：检查链表 B 的每个节点，看看是否存在于哈希集合中。
4. 返回结果：如果找到一个节点，立即返回该节点；如果遍历完整个链表 B 但没有找到，则返回 null。

Java 代码实现：

import java.util.HashSet;class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 检查链表是否为空if (headA == null || headB == null) {return null;}// 创建哈希集合HashSet<ListNode> seenNodes = new HashSet<>();// 将链表 A 中的所有节点存入哈希集合ListNode currentA = headA;while (currentA != null) {seenNodes.add(currentA);currentA = currentA.next;}// 遍历链表 B，查找是否有节点在哈希集合中ListNode currentB = headB;while (currentB != null) {if (seenNodes.contains(currentB)) {return currentB; // 找到交点}currentB = currentB.next;}return null; // 没有交点}
}

代码说明：

1. ListNode类：创建链表节点，包含一个整数值 val 和一个指向下一个节点的指针 next。
2. getIntersectionNode方法：
   • 首先检查两个链表是否为空。
   • 创建一个哈希集合 seenNodes，用于存放链表 A 的节点。
   • 遍历链表 A，将每个节点添加到集合中。
   • 然后遍历链表 B，检查每个节点是否在集合中，如果找到，返回该节点；如果遍历完链表 B 还没找到，则返回 null。

时间复杂度与空间复杂度：

• 时间复杂度：O(n + m)，其中 n 和 m 分别是链表 A 和 B 的长度，因为我们分别遍历了两个链表。
• 空间复杂度：O(n)，最坏情况下需要存储链表 A 的所有节点。因此，空间复杂度取决于链表 A 的长度。