单链表中间值（经典案例，5分钟解决）

一、题目描述

给定一个单链表，但不知该表的大小，现要求只遍历一次，找出位于单链表中间的值。

输入

1,8,7,6,4,5,3,1

输出

6

样例输入 Copy

1,2,4,8,9,6,3,1,0

样例输出 Copy

9

二、实现方法

普通方法：首先遍历一遍获取总长度L，然后再次遍历循环至L/2即可；时间复杂度为：O(L+L/2)=O(3/2L)

快速方法：快慢指针法，设置2个指针faster，mid都指向单链表的头节点，其中faster移动的速度为mid的2倍，当faster移动到末尾，mid即在中间位置了，以下是简单实现:

三、代码

1.节点定义

 static class LinkNode {
        int val;
        LinkNode next;
        public LinkNode(int val){
            this.val = val;
        }
    }

2. 定义两个节点，一个快节点，一个慢节点
 快的节点一次走两步；慢的节点一次走一步
 当快的节点走到链表的最后时，慢的节点刚好走到一半，即链表的中间节点

public static void FindMid(LinkNode first){
        LinkNode fast = first;
        LinkNode slow = first;
 
        while((fast != null)&&(fast.next != null)){
            fast = fast.next.next;
            slow = slow.next;
        }
        System.out.println(slow.val);
    }

3.测试方法

 public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next().toString();
        String[] arr  = str.split(",");
 
        int[] ints = new int[arr.length];
 
        for(int j = 0; j<ints.length;j++) {
            ints[j] = Integer.parseInt(arr[j]);
        }
        Stack<LinkNode> stack = new Stack<>();
        LinkNode head = new LinkNode(0);
        LinkNode p = head;
 
        for(int i = 0; i < ints.length; i++){
            p.next = new LinkNode(ints[i]);
            p = p.next;
            stack.add(p);
        }
        head = head.next;
        FindMid(head);
        }

4.完整代码

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    static class LinkNode {
        int val;
        LinkNode next;
        public LinkNode(int val){
            this.val = val;
        }
    }
    public static void FindMid(LinkNode first){
        LinkNode fast = first;
        LinkNode slow = first;
 
        while((fast != null)&&(fast.next != null)){
            fast = fast.next.next;
            slow = slow.next;
        }
        System.out.println(slow.val);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next().toString();
        String[] arr  = str.split(",");
 
        int[] ints = new int[arr.length];
 
        for(int j = 0; j<ints.length;j++) {
            ints[j] = Integer.parseInt(arr[j]);
        }
        Stack<LinkNode> stack = new Stack<>();
        LinkNode head = new LinkNode(0);
        LinkNode p = head;
 
        for(int i = 0; i < ints.length; i++){
            p.next = new LinkNode(ints[i]);
            p = p.next;
            stack.add(p);
        }
        head = head.next;
        FindMid(head);
        }
    }