검지Offer - 면접문제 6 끝에서 끝까지 체인 테이블 인쇄

1800 단어 알고리즘 문제

해법 1, 반복 인쇄 O (n)


사고방식: 체인 테이블과 나무는 매우 비슷해서 나무의 상용 해법을 연상하기 쉽다. 첫 번째 노드에 대해next값을 먼저 출력한 다음에 그 자체의 값을 출력한다. 마지막으로tail이 가장 먼저 출력하고head가 마지막에 출력한다.만약 체인 시계가 너무 길면, 귀속은 창고가 넘칠 수 있으니, 이런 방법은 적합하지 않다.
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        return printTtoH(new ArrayList<Integer>(), listNode);
    }

    ArrayList<Integer> printTtoH(ArrayList<Integer> printSeq, ListNode listNode) {
        if(listNode == null){
            return printSeq;
        }
        printSeq = printTtoH(printSeq, listNode.next);
        printSeq.add(listNode.val);
        return printSeq;

    }

해법 2, 인쇄된 시퀀스 O (n) 를 창고에 저장합니다.


전체 체인 테이블을 역으로 인쇄하고 체인 테이블의head를 지정합니다. 체인 테이블은 단방향 체인 테이블입니다. 넥스트 바늘만 있고 피할 수 없습니다. 체인 테이블에 정차적으로 접근해야 합니다.선진적 후출, 창고라는 데이터 구조가 있다.체인 테이블의 전체 값 서열을 창고에 저장하고 Pop 출력을 순서대로 하면 끝에서 끝까지 체인 테이블을 출력합니다.이런 해법은 첫 번째 안정성보다 낫다. 비록 한 번 더 순환하겠지만.

좋은 웹페이지 즐겨찾기