1. Introduction

1.介绍

In this tutorial, we’ll implement two linked list reversal algorithms in Java.

在本教程中，我们将在Java中实现两种链表反转算法。

2. Linked List Data Structure

2.链接的列表数据结构

A linked list is a linear data structure in which a pointer in each element determines the order. Each element of a linked list contains a data field to store the list data and a pointer field to point to the next element in the sequence. Also, we can use a head pointer to point to the start element of a linked list:

链接列表是一种线性数据结构，其中每个元素中的指针决定了顺序。链接列表的每个元素都包含一个数据字段来存储列表数据，以及一个指针字段来指向序列中的下一个元素。另外，我们可以使用一个head指针来指向链接列表的起始元素。

After we reverse the linked list, the head will point to the last element of the original linked list, and the pointer of each element will point to the previous element of the original linked list:

在我们反转链接列表后，head将指向原链接列表的最后一个元素，而每个元素的指针将指向原链接列表的前一个元素。

In Java, we have a LinkedList class to provide a doubly-linked list implementation of the List and Deque interfaces. However, we’ll use a general singly-linked list data structure in this tutorial.

在 Java 中，我们有一个 LinkedList 类来提供 List 和 Deque 接口的双链接列表实现。然而，在本教程中我们将使用一般的单链接列表数据结构。

Let’s first start with a ListNode class to represent an element of a linked list:

首先，让我们从一个ListNode类开始，以表示一个链表的元素。

public class ListNode {

    private int data;
    private ListNode next;

    ListNode(int data) {
        this.data = data;
        this.next = null;
    }

   // standard getters and setters
}

The ListNode class has two fields:

ListNode类有两个字段。

An integer value to represent the data of the element
A pointer/reference to the next element

A linked list may contain multiple ListNode objects. For example, we can construct the above sample linked list with a loop:

一个链接列表可以包含多个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. Iterative Algorithm Implementation

3.迭代算法的实现

Let’s implement the iterative algorithm in Java:

让我们在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;
}

In this iterative algorithm, we use two ListNode variables, previous and current, to represent two adjacent elements in the linked list. For each iteration, we reverse these two elements and then shift to the next two elements.

在这个迭代算法中，我们使用两个ListNode变量，previous和current，来代表链接列表中的两个相邻元素。在每次迭代中，我们将这两个元素反转，然后转移到下两个元素。

In the end, the current pointer will be null, and the previous pointer will be the last element of the old linked list. Therefore, previous is also the new head pointer of the reversed linked list, and we return it from the method.

最后，current指针将是null,，previous指针将是旧链接列表的最后一个元素。因此，previous也是反转链表的新头指针，我们从该方法中返回它。

We can verify this iterative implementation with a simple unit test:

我们可以用一个简单的单元测试来验证这个迭代的实现。

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

In this unit test, we first construct a sample linked list with five nodes. Also, we verify that each node in the linked list contains the correct data value. Then, we call the iterative function to reverse the linked list. Finally, we check the reversed linked list to make sure the data are reversed as expected.

在这个单元测试中，我们首先构建一个有五个节点的链接列表样本。同时，我们验证链表的每个节点都包含正确的数据值。然后，我们调用迭代函数来逆转链表。最后，我们检查反转的链表，以确保数据是按预期反转的。

4. Recursive Algorithm Implementation

4.递归算法的实现

Now, let’s implement the recursive algorithm in Java:

现在，让我们在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;
}

In the reverseListRecursive function, we recursively visit each element in the linked list until we reach the last one. This last element will become the new head of the reversed linked list. Also, we append the visited element to the end of the partially reversed linked list.

在reverseListRecursive函数中，我们递归地访问链表中的每个元素，直到到达最后一个。这最后一个元素将成为反转链表的新头。同时，我们将访问过的元素追加到部分反转的链表的末尾。

Similarly, we can verify this recursive implementation with a simple unit test:

同样地，我们可以用一个简单的单元测试来验证这个递归的实现。

@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. Conclusion

5.结论

In this tutorial, we implemented two algorithms to reverse a linked list. As always, the source code for the article is available over on GitHub.

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