반전 링크 세 가지 방법-자바

첫 번 째 방법:stack 사용
이 방법 은 추가 공간 이 필요 합 니 다.스 택 을 만 든 다음 에 스 택 에 스 택 을 옮 겨 다 니 고 이 어 스 택 을 꺼 내 다시 연결 하 며 두 번 옮 겨 다 녀 야 합 니 다.이런 방법 은 기술적 함량 이 별로 없 지만 견 디 지 못 하 는 사상 은 매우 간단 하 다.그래서 필기시험 에 부 딪 히 면 바로 쓸 수 있 고 면접 이 라면 이런 방법 만 제시 하면 거의 식 을 것 같 아 요....................................................
//      Stack    
    private static Node reverseList1(Node head) {
        if (head == null) return null;
        Stack stack = new Stack<>();
        Node cur = head;
        while ( cur != null ) {
            stack.push(new Node(cur.value));
            cur = cur.next;
        }
        cur = stack.pop();
        Node newHead = cur;
        while ( !stack.isEmpty() ) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        return newHead;
    }

두 번 째 방법:옮 겨 다 니 는 과정 에서 처음부터 반전(비 재 귀)
4.567917.먼저 하나의 변 수 를 사용 하여 현재 노드 의 다음 노드 를 저장 합 니 다
4.567917.이어서 다른 변수 로 현재 노드 의 앞 노드 를 저장 하고 현재 노드 의 next 를 앞 노드 로 가리킨다
4.567917.현재 노드 와 현재 노드 의 앞 노드 를 뒤로 이동 합 니 다
//           
    private static Node reverseList2(Node head) {
        Node pre = null;
        Node next = null;
        while ( head != null ) {
            next = head.next;//next  head     
            head.next = pre;//     next       ,    
            pre = head;//           
            head = next;//       
        }
        return pre;
    }

세 번 째 방법:끝 에서 끝까지 반전(재 귀)
이런 방법의 사상 은 재 귀적 인 방법 을 통 해 끝 에서 끝까지 옮 겨 다 니 는 것 이다.나 는 이런 방법 에 대한 이해 가 좋 지 않 기 때문에 다른 사람 을 오도 하지 않 는 다.여기에 설명 이 있 으 니 이 를 참고 하여 그의 사상 링크 가 뒤 집 힌 그림 설명(재 귀 와 교체 두 가지 실현)을 배 울 수 있다.
//          
    private static Node reverseList3(Node head) {
        if(head==null||head.next ==null)
            return head;
        Node next = head.next;
        Node prev = reverseList3(next);
        head.next.next = head;
        head.next = null;
        return prev;
    }

전체 테스트 코드:반전 링크
 

좋은 웹페이지 즐겨찾기