「算法与数据结构」链表

 1import java.util.*;
 2class Node{
 3    private final int value;
 4    private Node next;
 5    
 6    public Node(int value){
 7        this.value = value;
 8        this.next = null;
 9    }
10    public int getValue(){
11        return this.value;
12    }
13    public Node getNext(){
14        return this.next;
15    }
16    public void setNext(Node next){
17        this.next = next;
18    }
19    
20    public static void printLinkedList(Node head){
21        while(head != null){
22            System.out.print(head.getValue());
23            System.out.print(" ");
24            head = head.next;
25        }
26        System.out.println("");
27    }
28    
29}
30class LinkedListCreator{
31    public Node createLinkedList(List<Integer> data){
32        if(data.isEmpty()){
33            return null;
34        }
35        Node firstNode = new Node(data.get(0));
36        firstNode.setNext(createLinkedList(data.subList(1,data.size())));
37        return firstNode;                                          
38    }
39}
40
41class LinkedListReverser{
42    public Node reverseLinkedList(Node head){
43        if(head==null || head.getNext()==null){
44            return head;
45        }
46        Node newHead = reverseLinkedList(head.getNext());
47        head.getNext().setNext(head);
48        head.setNext(null);
49        return newHead;
50    }
51}
52
53public class Main {
54    public static void main(String[] args) {
55        LinkedListCreator creator = new LinkedListCreator();
56        LinkedListReverser reverser = new LinkedListReverser();
57        
58        // Node.printLinkedList(creator.createLinkedList(Arrays.asList(1)));
59        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(Arrays.asList(1,2,3,4,5))));
60        
61        System.out.println("Hello World!");
62    }
63}

  1import java.util.*;
  2
  3class Node {
  4    private Integer value;
  5    private Node next;
  6
  7    public Node(Integer value) {
  8        this.value = value;
  9        this.next = null;
 10    }
 11
 12    public Integer getValue() {
 13        return this.value;
 14    }
 15
 16    public void setNext(Node next) {
 17        this.next = next;
 18    }
 19
 20    public Node getNext() {
 21        return this.next;
 22    }
 23
 24    public static void printLinkedList(Node head) {
 25        while (head != null) {
 26            System.out.print(head.getValue());
 27            System.out.print(" ");
 28            head = head.getNext();
 29        }
 30        System.out.println();
 31    }
 32}
 33
 34class LinkedListCreator {
 35    public Node createLinkedList(List<Integer> data) {
 36        Node head = null;
 37        Node prev = null;
 38        for (Integer i : data) {
 39            Node node = new Node(i);
 40            if (prev != null) {
 41                prev.setNext(node);
 42            } else {
 43                head = node;
 44            }
 45            prev = node;
 46        }
 47        return head;
 48
 49    }
 50}
 51
 52class LinkedListReverser {
 53    public Node reverseLinkedList(Node head) {
 54        Node newHead = null;
 55        Node curHead = head;
 56        while (curHead != null) {
 57            Node node = curHead.getNext();
 58            curHead.setNext(newHead);
 59            newHead = curHead;
 60            curHead = node;
 61        }
 62        return newHead;
 63    }
 64}
 65
 66class LinkedListDeleter {
 67    public Node deleteIfEqual(Node head, int value) {
 68        while (head != null && head.getValue() == value) {
 69            head = head.getNext();
 70        }
 71        Node curNode = head;
 72        while (curNode.getNext() != null) {
 73            if (curNode.getNext().getValue() == value) {
 74                curNode.setNext(curNode.getNext().getNext());
 75            } else {
 76                curNode = curNode.getNext();
 77            }
 78        }
 79
 80        return head;
 81
 82    }
 83}
 84
 85public class Main {
 86
 87    public static Node deleteNodeEquals(Node head, int value){
 88        while(head != null && head.getValue() == value){
 89            head = head.getNext();
 90        }
 91        Node curNode = head;
 92        while(curNode.getNext() != null){
 93            if(curNode.getNext().getValue() == value){
 94                curNode.setNext(curNode.getNext().getNext());
 95            }else{
 96                curNode = curNode.getNext();
 97            }
 98        }
 99        return head;
100    }
101    public static void main(String[] args) {
102        LinkedListCreator creator = new LinkedListCreator();
103        LinkedListReverser reverser = new LinkedListReverser();
104        LinkedListDeleter deleter = new LinkedListDeleter();
105
106        Node.printLinkedList(creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5, 6)));
107        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5, 6))));
108        Node.printLinkedList(deleter.deleteIfEqual(creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5, 6)), 6));
109
110
111        Node.printLinkedList(deleteNodeEquals(creator.createLinkedList(Arrays.asList(1,2,3,4,5,6,7)), 5));
112
113        System.out.println("Hello World!");
114    }
115}