单链表反转(Singly Linked Lists in Java)

单链表反转(Singly Linked Lists in Java)

博客分类：

• 数据结构及算法

1. package dsa.linkedlist;
2. public class Node<E>{
3. E data;
4. Node<E> next;
5. }

1. package dsa.linkedlist;
2. public class ReverseLinkedListRecursively {
3. public static void main(String args[]) {
4. ReverseLinkedListRecursively reverser = new ReverseLinkedListRecursively();
5. SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);
6. System.out.println(“Original List : ” + originalList.toString());
7. originalList.start = reverser.reverse(originalList.start);
8. System.out.println(“Reversed List : ” + originalList.toString());
9. }
10. public Node<Integer> reverse(Node<Integer> list) {
11. if (list == null || list.next == null)
12. return list;
13. Node<Integer> nextItem = list.next;
14. list.next = null;
15. Node<Integer> reverseRest = reverse(nextItem);
16. nextItem.next = list;
17. return reverseRest;
18. }
19. private SinglyLinkedList<Integer> getLabRatList(int count) {
20. SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
21. for (int i = 0; i < count; i++) {
22. sampleList.add(i);
23. }
24. return sampleList;
25. }
26. }
27. /*
28. * SAMPLE OUTPUT Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Reversed List : 9,
29. * 8, 7, 6, 5, 4, 3, 2, 1, 0
30. */

1. package dsa.linkedlist;
2. /**
3. * This is a singly linked list with no prev pointer.
4. * @author Braga
5. * @param <E>
6. */
7. public class SinglyLinkedList<E> {
8. Node<E> start;
9. int size;
10. public SinglyLinkedList(){
11. start = null;
12. size = 0;
13. }
14. //insertAtLast
15. public void add(E data){
16. insertAtLast(data);
17. }
18. public void insertAtLast(E data){
19. if(size==0){
20. start = new Node<E>();
21. start.next = null;
22. start.data = data;
23. }else{
24. Node<E> currentNode = getNodeAt(size-1);
25. Node<E> newNode = new Node<E>();
26. newNode.data = data;
27. newNode.next = null;
28. currentNode.next = newNode;
29. }
30. size++;
31. }
32. public void insertAtFirst(E data){
33. if(size==0){
34. start = new Node<E>();
35. start.next = null;
36. start.data = data;
37. }else{
38. Node<E> newNode = new Node<E>();
39. newNode.data = data;
40. newNode.next = start;
41. start = newNode;
42. }
43. size++;
44. }
45. public Node<E> getNodeAt(int nodePos) throws ArrayIndexOutOfBoundsException{
46. if(nodePos>=size || nodePos<0){
47. throw new ArrayIndexOutOfBoundsException();
48. }
49. Node<E> temp = start;//Move pointer to front
50. int counter = 0;
51. for(;counter<nodePos;counter++){
52. temp = temp.next;
53. }
54. return temp;
55. }
56. public void insertAt(int position, E data){
57. if(position == 0){
58. insertAtFirst(data);
59. }else if(position==size-1){
60. insertAtLast(data);
61. }else{
62. Node<E> tempNode = getNodeAt(position-1);
63. Node<E> newNode = new Node<E>();
64. newNode.data = data;
65. newNode.next = tempNode.next;
66. tempNode.next = newNode;
67. size++;
68. }
69. }
70. public Node<E> getFirst(){
71. return getNodeAt(0);
72. }
73. public Node<E> getLast(){
74. return getNodeAt(size-1);
75. }
76. public E removeAtFirst(){
77. if(size==0){
78. throw new ArrayIndexOutOfBoundsException();
79. }
80. E data = start.data;
81. start = start.next;
82. size–;
83. return data;
84. }
85. public E removeAtLast(){
86. if(size==0){
87. throw new ArrayIndexOutOfBoundsException();
88. }
89. Node<E> tempNode = getNodeAt(size-2);
90. E data = tempNode.next.data;
91. tempNode.next = null;
92. size–;
93. return data;
94. }
95. public E removeAt(int position){
96. if(position==0){
97. return removeAtFirst();
98. }else if(position == size-1){
99. return removeAtLast();
100. }else{
101. Node<E> tempNode = getNodeAt(position-1);
102. E data = tempNode.next.data;
103. tempNode.next = tempNode.next.next;
104. size–;
105. return data;
106. }
107. }
108. public int size(){
109. return size;
110. }
111. public String toString(){
112. if(size==0){
113. return “”;
114. }else{
115. StringBuilder output = new StringBuilder();
116. Node<E> tempNode = start;
117. while(tempNode.next!=null){
118. output.append(tempNode.data).append(“, “);
119. tempNode = tempNode.next;
120. }
121. output.append(tempNode.data);
122. return output.toString();
123. }
124. }
125. }