用Java怎麼反轉鍊錶
- java
1.簡介
在本教程中，我們將在Java中實現兩個鍊錶反轉算法。
2.鍊錶數據結構
鍊錶是一種線性數據結構，其中每個元素中的指針確定順序。鏈接列表的每個元素都包含一個用於存儲列表數據的數據字段和一個指向該序列中的下一個元素的指針字段。另外，我們可以使用head指針指向鏈接列表的開始元素：
反轉鍊錶之後， head將指向原始鍊錶的最後一個元素，而每個元素的指針將指向原始鍊錶的前一個元素：
在Java中，我們有一個LinkedList類來提供List和Deque接口的雙鏈列表實現。但是，在本教程中，我們將使用常規的單鏈列表數據結構。
讓我們首先從ListNode類開始，以表示鏈接列表的元素：
public class ListNode {
private int data;
private ListNode next;
ListNode(int data) {
this.data = data;
this.next = null;
}
// standard getters and setters
}ListNode類具有兩個字段：
- 代表元素數據的整數值
- 指向下一個元素的指針/引用
鍊錶可能包含多個ListNode對象。例如，我們可以使用循環構造以上示例鏈接列表：
ListNode constructLinkedList() {
ListNode head = null;
ListNode tail = null;
for (int i = 1; i <= 5; i++) {
ListNode node = new ListNode(i);
if (head == null) {
head = node;
} else {
tail.setNext(node);
}
tail = node;
}
return head;
}3.迭代算法的實現
讓我們用Java實現迭代算法：
ListNode reverseList(ListNode head) {
ListNode previous = null;
ListNode current = head;
while (current != null) {
ListNode nextElement = current.getNext();
current.setNext(previous);
previous = current;
current = nextElement;
}
return previous;
}在此迭代算法中，我們使用兩個ListNode變量previous和current來表示鍊錶中的兩個相鄰元素。對於每次迭代，我們都將這兩個元素反轉，然後移至下兩個元素。
最後， current指針將為null,而previous指針將是舊鍊錶的最後一個元素。因此， previous也是反向鏈接列表的新頭指針，我們從方法中將其返回。
我們可以用一個簡單的單元測試來驗證這種迭代實現：
@Test
public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseList(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}在此單元測試中，我們首先構造一個具有五個節點的示例鏈接列表。另外，我們驗證鍊錶中的每個節點都包含正確的數據值。然後，我們調用迭代函數來反向鏈接列表。最後，我們檢查反向鏈接列表，以確保數據按預期反向。
4.遞歸算法的實現****
現在，讓我們在Java中實現遞歸算法：
ListNode reverseListRecursive(ListNode head) {
if (head == null) {
return null;
}
if (head.getNext() == null) {
return head;
}
ListNode node = reverseListRecursive(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return node;
}在reverseListRecursive函數中，我們以遞歸方式訪問鏈接列表中的每個元素，直到到達最後一個元素。最後一個元素將成為反向鏈接列表的新標題。同樣，我們將受訪元素附加到部分反向鍊錶的末尾。
同樣，我們可以使用簡單的單元測試來驗證此遞歸實現：
@Test
public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseListRecursive(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}