インバースチェーンテーブル

インバースチェーンテーブル
1.新しいチェーンテーブルを作成し、逆置きするチェーンテーブルを最后からノードを一つ一つ取り出し、新しいチェーンテーブルにテールを差し込むか、逆置きするチェーンテーブルを最初からノードを一つ一つ取り出し、新しいチェーンテーブルにヘッドを差し込む.2.スタックでチェーンテーブルの逆置きを実現し、チェーンテーブルの逆置きは前のチェーンテーブルを後ろに置くことであり、これはスタックの先進的な先出の特徴と一致する.

import java.util.Stack;

public class reverseList {
     
    static class Node {
     
        int val;
        Node next=null;
        Node(int val){
     
            this.val=val;
        }
    }
    //    
    public static Node reverseList(Node head){
     
        Stack<Node> stack=new Stack<>();

        Node cur=head;
        while (cur!=null){
     
            stack.push(cur);
            cur=cur.next;
        }
        Node newhead=null;
        Node last=null;
        while (!stack.isEmpty()){
     
            Node node=stack.pop();
            if(newhead==null){
     
                newhead=node;
                last=node;
            }else {
     
                last.next=node;
                last = node;
            }
        }
        last.next = null;//              null
        return newhead;
    }

    public static void main(String[] args) {
     
        Node n1=new Node(1);
        Node n2=new Node(2);
        Node n3=new Node(3);
        Node n4=new Node(4);
        Node n5=new Node(5);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        print(n1);
        Node head= reverseList(n1);
        print(head);
    }

    private static void print(Node newhead) {
     
        Node cur=newhead;
        while (cur!=null){
     
            if(cur.next == null) {
     
                System.out.println(cur.val);
                cur = cur.next;
            }else {
     
                System.out.print(cur.val + "-->");
                cur = cur.next;
            }

        }
    }
}

3.チェーンテーブルをその場で逆転する(新しい申請の新しい空間を使用しない)まず、現在のチェーンテーブルを巡回するノード(pcur)、現在のノードの次(next)、現在のノードの前(prev)を指す3つの参照を定義する.pcur.をnextで先にnextは、pcurを最後に更新するときに使用するために保存され、pcur.nextはprevを指し、pcurを更新します.注意:最後に希望する新しいチェーンテーブルのヘッダがこの3つの参照のどちらに指向されているかを確認する必要があります.

public class reverseLinklist {
     
    public static void main(String[] args) {
     
        Node head=new Node(1);
        Node n1=new Node(2);
        Node n2=new Node(3);
        Node n3=new Node(4);
        head.next=n1;
        n1.next=n2;
        n2.next=n3;
        Node newhead=reverse(head);
        Node cur=newhead;
        while (cur.next!=null){
     
            System.out.print(cur.val+"-->");
            cur=cur.next;
        }
        System.out.print(cur.val);

    }
    /*
    *     
    *     ，         
    * */
    public static Node reverse(Node head){
     
        Node pcur=head;
        Node prev=null;
        Node next;
        if(head==null||head.next==null){
     
            return head;
        }
        while (pcur!=null){
     
            /*if(pcur.next==null){     //             pcur   
                next=pcur.next;        //   pcur      
                pcur.next=prev;
                break;
            }*/
            next=pcur.next;
            pcur.next=prev;
            prev=pcur;
            pcur=next;   //         ，pcur       
        }
        return prev;     //              ，        
    }
    static class  Node {
     
        int val;
        Node next=null;
        Node(int val){
     
            this.val=val;
        }
    }
}