查找单链表的中间节点

雨点打透心脏的1/2处 2021-09-26 15:38 286阅读 0赞

这是今天面试测开面试官提到的一个问题，当时有点紧张，代码写的不整洁，回来整理了一下。个人有点强迫症，纸上的代码一定想用机器跑起来。特整理如下：  
问题描述：查找单链表的中间节点。  
我的思路：快慢指针。

“\`  
class Node \{  
int val ;  
Node next;  
public Node(int val) \{  
// TODO Auto-generated constructor stub  
this.val = val;  
this.next = null;  
\}  
\}  
public class Main \{

/**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Node head = new Node(1);
        Node a = new Node(2);
        Node b = new Node(3);
        Node c = new Node(4);
        Node d = new Node(5);
        Node e = new Node(6);
        head.next = a;//1-2 ==1
        System.out.println(findMid(head).val);
        a.next = b;//1-2-3 = 2
        System.out.println(findMid(head).val);
        b.next = c;//1-2-3-4 = 2
        System.out.println(findMid(head).val);
        c.next = d;//1-2-3-4-5 = 3
        System.out.println(findMid(head).val);
        d.next = e;//1-2-3-4-5-6 = 3
        System.out.println(findMid(head).val);
    }
    
    public static Node findMid(Node head) {
        if(head==null)
            return null;
        Node p1 = head;//慢指针
        Node p2 = head.next;//快指针 偶数长度是显示中间节点的第一个 如1-2-3-4 中间节点为2 
        while(p2!=null){
            p2 = p2.next;
            if(p2!=null){
                p2 = p2.next;   
                p1 = p1.next;
            }
        }
        return p1;      
    }