在处理链表问题时,常常会遇到需要找到链表中点的情况。这里我们讨论四种常见的情况,并提供了相应的Java代码实现。
1. 寻找链表的中点或上中点
在链表节点数量为奇数时,中点只有一个;为偶数时,我们定义第 N/2
个节点为上中点。
public static Node midOrUpMidNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return head;}Node slow = head.next;Node fast = head.next.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}
2. 寻找链表的中点或下中点
在链表节点数量为偶数时,我们定义第 N/2 + 1
个节点为下中点。
public static Node midOrDownMidNode(Node head) {
if (head == null || head.next == null) {return head;}Node slow = head.next;Node fast = head.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}
3. 寻找链表的中点或上中点的前一个节点
public static Node midOrUpMidPreNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node slow = head;Node fast = head.next.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}
4. 寻找链表的中点或下中点的前一个节点
public static Node midOrDownMidPreNode(Node head) {if (head == null || head.next == null) {return null;}if (head.next.next == null) {return head;}Node slow = head;Node fast = head.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}
以上四种方法的核心思想都是利用快慢指针。快指针每次走两步,慢指针每次走一步。当快指针走到链表尾部时,慢指针正好在链表的中点。在处理链表问题时,快慢指针是一个非常常用也非常有效的技巧。
以上就是链表中点查找的四种常见情况的Java实现,希望对大家有所帮助。