자바 단일 체인 테이블 반전 실현

1683 단어 데이터 구조
질문
1. 문제 설명
1 - - > 2 - > 3 - > 4 - > 5 - > null 과 같은 단 방향 링크 를 반전 시 킵 니 다.
뒤 집 힌 결 과 는 5 - > 4 - > 3 - > 2 - > 1 - > null 입 니 다.
2. 해결 방안
링크 
링크 를 배열 로 나 눈 다음 에 배열 의 역 서 를 링크 로 조립 하 다.
이 방법 은 간단 하고 지침 이 많이 필요 없 으 며 n 개 단위 의 공간 이 필요 하 다 는 단점 이 있다.
B 포인터 역순
세 개의 지침 은 각각 현재 노드 (p), 현재 노드 의 다음 노드 (q), q 의 다음 노드 (r) 를 가리킨다.r 의 존 재 는 q 의 next 포인터 가 p 를 가리 킬 때 원래 q 의 next 값 을 잃 어 버 리 지 않 습 니 다.원본 코드 는 다음 과 같다.
public class Node {

    public int value;
    public Node next;

    public Node(int value) {
        this.value = value;
    }

    public boolean hasNext() {
        return next != null;
    }
}
private static Node reverse(Node node) {
        Node p = node;
        Node q = p.next;
        Node r;

        p.next = null;
        while (q != null) {
            r = q.next;
            q.next = p;
            p = q;
            q = r;
        }
        return p;
    }

C 재 귀 법
먼저, 첫 번 째 노드 뒤의 부분 D 를 하나의 전체 로 보고 D 는 이미 역순 이 라 고 생각한다. 지금 해 야 할 일 은 첫 번 째 노드 와 D 노드 로 구 성 된 링크 를 역순 으로 하 는 것 이다.
그 다음 에 D 노드 내부 에 대해 역 순 서 를 하고 똑 같은 사고 로 처리 해 야 한다.
다시 한 번, 재 귀 출구 는 D 노드 의 next 가 비어 있 을 때 D 노드 가 마지막 노드 라 는 것 을 설명 하고 바로 돌아 가면 됩 니 다.
원본 코드 는 다음 과 같 습 니 다.
/**
     *
     * @param node      
     * @param pre           
     * @return
     */
    private static Node reverseRecursion(Node node, Node pre) {
        Node head = node;
        Node pnext = head.next;
        head.next = pre;
        if (pnext == null) {
            return head;
        }
        return reverseRecursion(pnext, head);
    }

이상
IL_System View 와 Control
마늘 손님 접 룡 (띠 권 및 템 플 릿 문제 수집)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage