题目描述:
思路:
①:遍历一遍,得到链表总长,然后再遍历到一半的位置。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
int len = 1;
for(ListNode temp = head; temp.next!=null; temp=temp.next){
len++;
}
int n = (len-1)/2;
System.out.println(n);
for(int i =0;i<n;i++){
head = head.next;
}
//如果是偶数
if((len&1)==0){
return head.next;
}else{
return head;
}
}
}
②:快慢指针法:快指针一次走两步,慢指针一次走一步。这样当快指针到链表末尾时(奇数个),慢指针在链表中间。如果是偶数,慢指针再向前走一步。
这个方法比较快:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = head;
ListNode slow = head;
while(fast.next!=null){
if(fast.next.next!=null){
fast=fast.next.next;
slow = slow.next;
}else{
fast= fast.next;
slow=slow.next;
}
}
return slow;
}
}