단 방향 링크 의 중간 결산 점 을 구하 다.

단 방향 링크 의 중간 결산 점 을 구하 다.
수요
비어 있 지 않 은 단 방향 링크 는 중간 노드 로 돌아 갑 니 다.만약 두 개의 중간 결점 이 있다 면,두 번 째 결점 으로 돌아 가라.링크 크기 는 1~100 사이 로 조절 합 니 다.
예시 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])

예시 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])

방법 1:배열 로 구현
순환 적 으로 링크 를 옮 겨 다 니 며 링크 의 길 이 를 통계 하 는 동시에 모든 노드 를 배열 에 저장 하고 마지막 으로 배열 의 각 표 지 를(링크 길이/2)의 결점 으로 되 돌려 주면 됩 니 다.

    /**
     *           ，      
     * @param head
     * @return
     */
    public SingleNode middleNodeByArrays(SingleNode head) {
        SingleNode[] arrays = new SingleNode[100];
        int count = 0;
        while (head != null) {
            arrays[count] = head;
            count++;
            head = head.next;
        }
        return arrays[count / 2];
    }

테스트 코드:

        //           
        SingleLinkedList sll1 = new SingleLinkedList();
        for (int i = 1; i < 10; i++) {
            SingleNode node = new SingleNode(i, null);
            sll1.add(node);
        }
        System.out.println(sll1.toString());

        SingleNode node1 = middleNodeByArrays(sll1.getFirst());
        sll1.logFromHead("middleNodeByArrays1", node1);

        SingleLinkedList sll2 = new SingleLinkedList();
        for (int i = 1; i < 11; i++) {
            SingleNode node = new SingleNode(i, null);
            sll2.add(node);
        }
        System.out.println(sll2.toString());

        SingleNode node2 = middleNodeByArrays(sll2.getFirst());
        sll2.logFromHead("middleNodeByArrays2", node2);

출력 결과:예상 에 부합 합 니 다.

    SingleLinkedList:[1, 2, 3, 4, 5, 6, 7, 8, 9]
    middleNodeByArrays1:[5, 6, 7, 8, 9]
    SingleLinkedList:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    middleNodeByArrays2:[6, 7, 8, 9, 10]

방법 2:빠 르 고 느 린 지침 사용
두 개의 포인터 slow 와 fast 를 정의 합 니 다.slow 는 한 걸음 씩 이동 합 니 다.fast 는 두 걸음 씩 이동 합 니 다.그러면 fast 끝 점 이 있 을 때 slow 는 반드시 링크 의 중간 점 에 있 습 니 다.코드 는 다음 과 같 습 니 다:

    /**
     *           ，        
     * @param head
     * @return
     */
    public SingleNode middleNodeByTwoPointers(SingleNode head) {
        SingleNode slow = head;
        SingleNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

테스트 코드 는 다음 과 같 습 니 다:

         //           
        SingleLinkedList sll1 = new SingleLinkedList();
        for (int i = 1; i < 10; i++) {
            SingleNode node = new SingleNode(i, null);
            sll1.add(node);
        }
        System.out.println(sll1.toString());

        SingleNode node1 = middleNodeByTwoPointers(sll1.getFirst());
        sll1.logFromHead("middleNodeByTwoPointers1", node1);

        SingleLinkedList sll2 = new SingleLinkedList();
        for (int i = 1; i < 11; i++) {
            SingleNode node = new SingleNode(i, null);
            sll2.add(node);
        }
        System.out.println(sll2.toString());
        SingleNode node2 = middleNodeByTwoPointers(sll2.getFirst());
        sll2.logFromHead("middleNodeByTwoPointers2", node2);

출력 결 과 는 다음 과 같 습 니 다:예상 에 부합 합 니 다.

    SingleLinkedList:[1, 2, 3, 4, 5, 6, 7, 8, 9]
    middleNodeByTwoPointers1:[5, 6, 7, 8, 9]
    SingleLinkedList:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    middleNodeByTwoPointers2:[6, 7, 8, 9, 10]

전체 코드 확인
프로젝트 에서 SingleLinkedList 를 검색 하면 됩 니 다.github 전송 문https://github.com/tinyvampirepudge/DataStructureDemo
gitee 전송 문https://gitee.com/tinytongtong/DataStructureDemo
참고:1,middle-of-the-linked-list
2.자바 를 사용 하여 단 방향 링크 를 실현 하고 링크 반전 을 완성 합 니 다.