[JAVA] 링크드리스트(linkedList) 중간 Node 구하기

LinkedList에서 빠른포인터와 느린포인터를 사용하여서 중간노드를 구하는 방법

느린포인터가 한 칸 갈때, 빠른포인터는 두 칸 증가한다.

빠른포인터가 마지막에 다달았을때, 느린포인터가 가르키는 위치가 중간 노드

우선, 테스트에 필요한 구현체 구현 

- 간단한 Node 클래스

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

- 1~7까지의 linkedList 생성

public static Node makeLinkedList(){
    Node head = new Node(1);
    Node node1 = new Node(2);
    Node node2 = new Node(3);
    Node node3 = new Node(4);
    Node node4 = new Node(5);
    Node node5 = new Node(6);
    Node node6 = new Node(7);
    
    head.next = node1;
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node6;
    
    return head;
}

- 빠른포인터와 느린포인터를 사용하여 중간노드를 얻는 getMiddle() 메소드 구현

public static Node getMiddle(Node head){
    if(head == null){
        return head;
    }
    Node fastPtr = head.next;
    Node slowPtr = head;
    
    while(fastPtr != null){
        fastPtr = fastPtr.next;
        if(fastPtr != null){
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next;
        }
    }
    
    return slowPtr;
}

- 테스트

public static void main(String[] args){
    Node head = makeLinkedList();
    Node middle = getMiddle(head);
    System.out.println(middle.val);
}

중간값인 4가 나옴