데이터 구조의 링크 면접 문제 집합 (1) - 단 방향 링크 의 중간 노드, 마지막 K 번 째 노드 찾기

date: 2016 - 08 - 18 9: 12: 22 title: 데이터 구조의 링크 면접 문제 집합 (1) – 단 방향 링크 의 중간 노드, 마지막 K 번 째 노드 categories: 데이터 구조 찾기
저작권 성명: 본 사 이 트 는 개방 적 인 [지식 공유 서명 - 비 상업 적 사용 - 동일 방식 공유 허가 협의] 로 허 가 를 진행 합 니 다.
모든 글 에 나타 난 코드 는 제 github 에 나타 날 것 입 니 다. 이름 은 클래스 전체 이름 에 따라 찾 을 수 있 습 니 다. 저 는 github 에 있 는 폴 더 에 도 디 렉 터 리 설명 을 추가 할 것 입 니 다.
이 글 은 주로 단 방향 링크 의 응용 을 토론 하 는데 대체적으로 글 목록 구 조 를 보십시오.또한 관련 방법 에 서 는 용기 에 의 해 데 이 터 를 저장 하지 않 고 사용 할 수 있 도록 한다.각 시리즈 의 참고 자 료 는 모두 번호 가 가장 큰 문장 안에 있 습 니 다. 만약 에 이 문장 특유 의 것 이 라면 문장의 끝 부분 에 있 는 참고 자 료 를 보십시오.
단 방향 링크 의 생 성과 옮 겨 다 니 기 (가장 기본 적 이 고 상식 지식 에 속 합 니 다)

/**
 *       
 * 
 * @author XinPan
 * 
 */
public class Node {
    //       
    int record;
    //                
    Node next;

    // ------getter&setter-------------
    public int getRecord() {
        return record;
    }

    public void setRecord(int record) {
        this.record = record;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node(int record) {
        super();
        this.record = record;
    }
}

/**
 *       
 * 
 * @author XinPan
 * 
 */
public class RecustionAllElementOfLinkedList {

    //         
    public static void printAllElements(Node head) {

        while (head != null) {

            System.out.println(head.getRecord());

            head = head.getNext();
        }
    }

    //          
    public static int sizes(Node head) {
        int length = 0;
        if (head == null)
            return length;
        while (head != null) {
            length++;
            head = head.getNext();
        }
        return length;
    }
}

단일 체인 테이블 의 마지막 k 번 째 결점 찾기 (검 지 offer, 문제 15)
생각:
1. 링크 의 노드 를 배열 에 저장 한 다음 에 배열 을 통 해 length - k 비트 요 소 를 얻 는 것 을 고려 하지만 이런 방법 은 모든 노드 를 배열 에 넣 고 메모 리 를 낭비 해 야 한다.
2. 용 기 를 빌려 노드 를 저장 하 는 방법 을 부정 한 이상 어떤 방식 으로 마지막 K 번 째 노드 를 얻 을 수 있 습 니까?
3. 링크 자체 의 구 조 를 바 꾸 지 않 고 용 기 를 빌 리 지 않 는 다 는 점 을 감안 하여 '포인터' 를 빌려 이 문 제 를 완성 할 수 있 습 니 다.
4. 두 번 의 링크 를 옮 겨 다 니 며 링크 의 총 길 이 를 얻 은 후에 다시 한 번 옮 겨 다 니 며 제 length - k 개의 노드 를 옮 겨 다 니 고 돌아 갈 수 있 습 니 다. 그러나 이런 방법 은 소모 가 너무 많 습 니 다.
5. 두 개의 '포인터' 를 빌려 링크 에서 한 개의 발 표 지 를 k 번 째 노드 로 이동 시 킨 다음 에 첫 번 째 '포인터' 와 함께 이동 할 수 있다. 뒤의 '포인터' 가 링크 의 마지막 노드 에 이 르 렀 을 때 앞의 '포인터' 에 해당 하 는 노드 로 돌아 갈 수 있다.
도해: 예 - 마지막 두 번 째 노드 가 져 오기

public class FindReciprocalElementOFLinkedList {
    /**
     *           k   
     * @param head       
     * @param k         
     * @return
     */
    public static Node find(Node head, int k) {
        //         k=0,   
        if (head == null || k == 0)
            throw new RuntimeException(
                    "check your parms that was sent to this method");

        //                 
        Node first = head;
        Node second = head;

        //  second“  ”     k-1  
        for (int i = 1; i < k; i++) {
            second = second.getNext();

            //   :k             ，         
            if (second == null)
                throw new RuntimeException(
                        "the k is more than the size of this list");
        }

        //                               
        while (second.getNext() != null) {
            first = first.getNext();
            second = second.getNext();
        }

        //          ，     k   
        return first;

    }

}

테스트 코드:

public class ReverseLinkedListTest {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);

        System.out.println(FindReciprocalElementOFLinkedList.find(node1, 2)
                .getRecord());
    }

}

실행 결과:
단 방향 링크 의 중간 노드 찾기
생각:
1. 우 리 는 지난 문제 에서 쌍 지침 을 사용 하 는 사상 을 계승 하여 실현 할 수 있다. 그러면 메모리 도 절약 할 수 있 고 효율 도 높 일 수 있다.
2. 한 바늘 로 한 자 리 를 이동 시 키 고 다른 바늘 로 두 자 리 를 이동 시 킵 니 다. 이동 범위 가 큰 바늘 이 끝 에 도 달 했 을 때 앞 에 있 는 지침 에 대응 하 는 노드 가 바로 중간 노드 입 니 다!
도해:
코드 구현:

public class FindTheMidElement {

    public static Node findMidNode(Node head) {

        //   head    ，     
        if (head == null)
            throw new RuntimeException("     ");

        //            “  ”，          
        Node first = head;
        Node second = head;

        //                              ，
        while (second != null && second.getNext() != null) {

            //            ，          
            first = first.getNext();
            second = second.getNext().getNext();
        }

        //              ，         
        return first;
    }
}

테스트 코드: 노드 수가 기수 일 때:

public class ReverseLinkedListTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);

        System.out.println(FindTheMidElement.findMidNode(node1).getRecord());
    }

}

실행 결과:
노드 수가 짝수 일 때:

public class ReverseLinkedListTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);

        System.out.println(FindTheMidElement.findMidNode(node1).getRecord());
    }

}

실행 결과: