我正在使用Java来实现这个项目,采用测试驱动开发的方法,因此也附带了测试用例。
表示单个节点的Node类 -
package com.adnan.linkedlist;
public class Node {
public Node(int value, Node node){
this.value = value;
this.node = node;
}
private int value;
private Node node;
public int getValue() {
return value;
}
public Node getNode() {
return node;
}
public void setNode(Node node){
this.node = node;
}
}
服务类,以起始节点作为输入并在不使用额外空间的情况下将其保留。
package com.adnan.linkedlist;
public class SinglyLinkedListReversal {
private static final SinglyLinkedListReversal service
= new SinglyLinkedListReversal();
public static SinglyLinkedListReversal getService(){
return service;
}
public Node reverse(Node start){
if (hasOnlyNodeInLinkedList(start)){
return start;
}
Node firstNode, secondNode, thirdNode;
firstNode = start;
secondNode = firstNode.getNode();
while (secondNode != null ){
thirdNode = secondNode.getNode();
secondNode.setNode(firstNode);
firstNode = secondNode;
secondNode = thirdNode;
}
start.setNode(null);
return firstNode;
}
private boolean hasOnlyNodeInLinkedList(Node start) {
return start.getNode() == null;
}
}
并且覆盖上述场景的测试用例。请注意,您需要junit jars。我正在使用testng.jar;您可以使用任何您喜欢的。
package com.adnan.linkedlist;
import org.testng.annotations.Test;
import static org.testng.AssertJUnit.assertTrue;
public class SinglyLinkedListReversalTest {
private SinglyLinkedListReversal reversalService =
SinglyLinkedListReversal.getService();
@Test
public void test_reverseSingleElement() throws Exception {
Node node = new Node(1, null);
reversalService.reverse(node);
assertTrue(node.getNode() == null);
assertTrue(node.getValue() == 1);
}
@Test
public void test_reverseThreeElement() throws Exception {
Node node3 = new Node(3, null);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 3; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
@Test
public void test_reverseFourElement() throws Exception {
Node node4 = new Node(4, null);
Node node3 = new Node(3, node4);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 4; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
@Test
public void test_reverse10Element() throws Exception {
Node node10 = new Node(10, null);
Node node9 = new Node(9, node10);
Node node8 = new Node(8, node9);
Node node7 = new Node(7, node8);
Node node6 = new Node(6, node7);
Node node5 = new Node(5, node6);
Node node4 = new Node(4, node5);
Node node3 = new Node(3, node4);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 10; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
@Test
public void test_reverseTwoElement() throws Exception {
Node node2 = new Node(2, null);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 2; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
}