在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中实现iterative算法。

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();
    }
}

5.总结

在本教程中，我们实现了两种算法来逆转一个链表。一如既往，文章的源代码在GitHub上。

1.绪论

2.链表的数据结构

3.迭代算法的实现

4.递归 算法实现

5.总结

4.递归算法实现