데이터 구조 반전 단 방향 링크 와 양 방향 링크

3304 단어 데이터 구조
프로그래머 코드 면접 안내 (좌 정 운) 독서 노트
 제3 장
반전 단 방향 링크 와 양 방향 링크
//단 방향 링크
public class Node {
 public int value;
 public Node next;
 public Node(int data){
     this.value=data;
 }
}
public class ReturnList {
public static void main(String[] args) {
    Node no1=new Node(2);
    Node no2=new Node(3);
    Node no3=new Node(4);
    Node no4=new Node(5);
    no1.next=no2;
    no2.next=no3;
    no3.next=no4;
    System.out.println(no1.value+"-"+no1.next.value+"-"+no1.next.next.value);
Node nn=    reList(no1);
System.out.println(nn.value+"-");
}
public static Node reList(Node head){
    //head 가 비어 있 으 면 head 로 돌아 갑 니 다.
    if(head==null){
        return head;
    }
    //역순 후의 첫 번 째 노드
    Node pre=null;
    Node next=null;
    while(head!=null){
        //next 로 head 의 next 노드 를 저장 하지만 링크 는 끊 어 지지 않 습 니 다.
        next=head.next;
        //head 의 next 노드 가 pre 를 가리 키 고 있 습 니 다.
        head.next=pre;
        //교환 값, 다음 반전
        pre=head;
        head=next;
    }
    return pre;
}
}
//양 방향 링크
public class DoubleNode {
  public int value;
  public DoubleNode last;
  public DoubleNode next;
  public DoubleNode(int data){
      this.value=data;
  }
}
public class ReturnDoubleList {
  public static void main(String[] args) {
}
  public static DoubleNode reverList(DoubleNode head){
      DoubleNode pre=null;
      DoubleNode next=null;
      while(head!=null){
          next=head.next;
          head.next=pre;
          head.last=next;
          pre=head;
          head=next;
      }
      return pre;
  }
}
반전 부분 단 방향 링크
   단 방향 링크 의 머리 노드 head 와 두 개의 정수 from 과 to 를 지정 하고 단 방향 링크 에서 두 번 째 노드 를 to 노드 로 반전 시 킵 니 다.
예: 1 -> 2 -> 3 -> 4 -> 5 -> null ,  form=2  to=4
     반전 후: 1 -> 4 -> 3 -> 2 -> 5 -> null
public class Node {
 public int value;
 public Node next;
 public Node(int data){
     this.value=data;
 }
}
package com.chen.homework;
public class ReturnSomeList {
   public static void main(String[] args) {
}
   public static Node returnSomeNode(Node head,int from,int to){
       int len=0;
       Node node1=head;
       Node fPre=null;
       Node tPos=null;
       while(node1!=null){
           len++;
           fPre=len==from-1?node1:fPre;
           tPos=len==to+1?node1:tPos;
           node1=node1.next;
       }
       if(from>to || from<1 || to>len){
           return head;
       }
       node1=fPre==null?head:fPre.next;
       Node node2=node1.next;
       node1.next=tPos;
       Node next=null;
       while(node2!=tPos){
           next=node2.next;
           node2.next=node1;
           node1=node2;
           node2=next;
       }
       if(fPre!=null){
           fPre.next=node1;
           return head;
       }
       return node1;
   }
}

좋은 웹페이지 즐겨찾기