[검 지 offer]체인 테이블 01:끝 에서 끝까지 체인 테이블 인쇄

제목 설명
링크 를 입력 하고 링크 값 이 끝 에서 끝까지 의 순서에 따라 Array List 를 되 돌려 줍 니 다.
문제 풀이 아이디어(Java)
1)창 고 를 이용 하여 실현 한다.2)Collections 로 클래스 집합 하기;3)세 개의 지침 을 이용 하여 체인 시 계 를 반전 시 키 는데 관건 은 r 지침 이 끊 어 진 노드 를 저장 하 는 것 이다.4)재 귀 를 통 해 실현(재 귀 의 본질 은 스 택 구 조 를 사용 했다)
4.567917.통일 정의:4.567918.

/**
 *     ListNode 
 * @author     
 *
 */    
class ListNode{
  int val; //   
  ListNode next = null; //    

  public ListNode(int val) {
    this.val=val;
  }
}

4.567917.1)스 택 을 이용 하여 실현 한다

public class Demo01 {
  public static  ArrayList printListFromTailToHead(ListNode listNode) {
    Stack stack = new Stack();
    ArrayList list = new ArrayList();
    while(listNode!=null) {
        stack.push(listNode.val);
        listNode=listNode.next;     
    }
    while(!stack.isEmpty()) {
        list.add(stack.pop());
    }   
    return list;
  }
}

2)Collections 집합 류 로

public class Demo01 {
  public static  ArrayList printListFromTailToHead(ListNode listNode) {
     ArrayList list = new ArrayList();
     while(listNode!=null) {
        list.add(listNode.val);
        listNode=listNode.next;
     }
     Collections.reverse(list);     
     return list;
  } 
}

4.567917.3)세 개의 지침 을 이용 하여 체인 시 계 를 반전 시 키 는데 관건 은 r 지침 이 끊 어 진 노드 를 보존 하 는 것 이다

public class Demo01 {
  public static  ArrayList printListFromTailToHead(ListNode listNode) {
    if(listNode == null)
        return new ArrayList();
    ListNode head = listNode;
    ListNode cur = listNode.next;
    while(cur!= null){
        ListNode temp = cur.next;
        cur.next = head;
        head = cur;
        cur = temp;
    }
    //  listNode next      node，    listNode.next=null,    
    listNode.next = null;
    ArrayList res = new ArrayList();
    while(head !=null){
        res.add(head.val);
        head = head.next;
    }
    return res;
  }
}

4.567917.4)재 귀 를 통 해 실현(재 귀 의 본질 은 스 택 구 조 를 사 용 했 습 니 다)

public class Demo01 {
  public static ArrayList printListFromTailToHead(ListNode listNode) {
    ArrayList list=new ArrayList();
    ListNode pNode=listNode;
    if(pNode!=null){
        if(pNode.next!=null){
            list=printListFromTailToHead(pNode.next);
        }
        list.add(pNode.val);
    }

    return list;
  }
}

테스트 주 방법

public static void main(String[] args) {
    ListNode listNode = new ListNode(1);
    ListNode listNode2 = new ListNode(2);
    ListNode listNode3 = new ListNode(3);
    ListNode listNode4 = new ListNode(4);
    listNode3.next = listNode4;
    listNode2.next = listNode3;
    listNode.next = listNode2;
    System.out.println(printListFromTailToHead(listNode));
  }