我正在尝试找到单链表的中间部分。这直接来自这个leetcode问题。
我知道如何使用列表来计算它,但我想知道为什么我的解决方案不起作用。
这是ListNode类
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
这是我的源代码
public class middle_linked_list {
public static void main(String args[]){
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
System.out.println(middleElement(head).val);
}
public static ListNode middleElement(ListNode head){
int size = 0;
float counter = 0;
float middle = 0;
ListNode mid = head;
while(head != null)
{
++size;
head = head.next;
}
if(size % 2 == 0){
middle = size/2f;
}else{
middle = Math.round(size/2f);
}
while(mid != null){
if(counter == middle)
{
System.out.println(mid.val);
return mid;
}
System.out.println(mid.val);
++counter;
mid = mid.next;
}
return null;
}
}
我的方法
有人可以向我解释为什么我的代码不起作用
它适用于这样的例子 [1,2,3,4] 和 [1,2,3,4,5,6] (基本上适用于所有偶数列表大小),但不适用于 1,2,3,4,5,6,7
干杯,非常感谢
你说你的代码不起作用,但这不是真的,它起作用了,只是没有达到预期,尝试在未来更清楚地了解问题。
无论如何,只需将计数器初始化为 1,而不是 0,然后就可以开始了。
--编辑--
正如我所说,它在我的电脑上运行得很好,这是使用 == 运算符比较两个浮点数的问题。它可能对某些系统或 JRE 来说可以按需要工作,但对其他系统则不然,据我所知,这与 Java 无关(Javascript 的行为是一样的),它与浮点数小数部分的二进制表示有关在每个不同的系统中,这是一个高级且非常低级的主题,这种类型,我们作为开发人员,谢天谢地,不需要深入研究来处理,我们只需要现在它存在并相应地处理它。对于您的代码,无需使用浮点数,使用整数将解决问题并使该解决方案适用于任何系统。
如果您想了解更多,请查看链接:
https://howtodoinjava.com/java-examples/ Correctly-compare-float-double/
我冒昧地更改了代码中的一些其他内容,作为 Java 的良好实践,请参阅评论:
class ListNode {
//For the sake of encapsulation always keep class variables/attributes
//as private and provide get/set methods as needed to access/update
//private values
private int val;
private ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
//getters and setters
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
/* this constructor is mostly useless, you don't know who next is
* before instantiating it, and if you instantiate next at the same
* time as the current node then what will you do about next of next?
* And what about next of next of next and so on? See the problem?
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}*/
}
//As a convention always use CamelCase for Java names, this
//will also require you to rename the file to MiddleLinkedList.java
public final class MiddleLinkedList {
public static void main(String[] args) {
/* make the instantiating dynamic, instead of fixed
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
*/
//dynamically instantiating n nodes:
int val = 1;
int n = 7; //total list size
ListNode head = new ListNode(val);
ListNode node = head;
val++;
for (; val <= n; val++) {
node.setNext(new ListNode(val)); //set next node
//"node" variable becomes next for the next loop iteration
node = node.getNext();
}
System.out.println("middle found: " + middleElement(head).getVal());
}
public static ListNode middleElement(final ListNode head) {
//As a good practice it's better to declare parameters as final,
//that means you won't be able to reassign the head parameter
int size = 0;
//Don't use float or double when you're going to compare values,
//if you need to compare float numbers don't use ==, a different
//technique is required.
//Changing variables to int:
int counter = 1;
int middle = 0;
ListNode mid = head;
while (mid != null) {
//I usually favor post-increment (size++) over pre-increment
//(++size), but these only become a issue when you assign the
//increment or mix it with other operations, example:
//(x = y++) is not the same as (x = ++y)
//just as (x + y++) is not the same as (x + ++y)
size++;
//we can't reassign head, since we changed it to final, so we
//need to work with a different variable:
//head = head.getNext();
mid = mid.getNext();
}
/* this whole block can be replaced by a single line, see the
* next statement
if (size % 2 == 0) {
middle = size / 2f;
} else {
middle = Math.round(size / 2f);
}
*/
//the division between two integers is always truncated, not
//rounded, truncating a number means any decimal value will
//be discarded, example: 1.999, will still be 1.
//the (size % 2) part will add the rest, 0 if even size, 1 if odd
middle = (size / 2) + (size % 2);
//again we set mid to the first element to iterate and find
//the middle one
mid = head;
while (mid != null) {
//comparing int or long with == is safe and predicted, don't
//use == to compare float or double
if (counter == middle) {
System.out.println("the middle value is: "
+ mid.getVal());
return mid;
}
System.out.println("not the middle value: "
+ mid.getVal());
//again, I recommend sticking to post-increment, just because
//is what most people do, these increments can be confusing
//and the source of some annoying bugs
counter++;
mid = mid.getNext();
}
return null;
}
}
class Solution {
// Method to find the middle node of a linked list
public ListNode findMiddleNode(ListNode head) {
// Initialize two pointers, slowPointer and fastPointer, both pointing to the head of the list
ListNode slowPointer = head;
ListNode fastPointer = head;
// Traverse the linked list with two pointers
// The slowPointer moves one node at a time, while the fastPointer moves two nodes at a time
// When the fastPointer reaches the end of the list, the slowPointer will be at the middle node
while (fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next; // Move slowPointer one step forward
fastPointer = fastPointer.next.next; // Move fastPointer two steps forward
}
// Return the node pointed by slowPointer, which is the middle node of the linked list
return slowPointer;
}
}
这适用于奇数个元素以及偶数个元素。 如果元素个数为奇数,它将给出正好中间的元素,如果元素个数为偶数,它将给出第二个中间元素。
假设 1->2->3->4->5->6->7 (说明:元素个数为奇数,因此返回 4)
1->2->3->4->5->6->7->8 (说明:元素个数为偶数,因此返回 5,即中间第二个元素)
注意: fastPointer != null 确保只要 fastPointer 不为 null,循环就会继续。这可以防止访问 fastPointer.next 时出现空指针异常。
fastPointer.next != null 确保我们可以安全地访问 fastPointer.next 而不会遇到空指针异常。这种情况可以防止访问 fastPointer.next.next 时出现空指针异常。