反转链表Java实现

链表是一种常见的数据结构，其特点是可以快速地插入、删除数据。在编程面试中，反转链表常常是经常出现的问题，今天我们来学习如何使用Java实现链表反转。

什么是链表

链表是一种线性结构，其由节点组成，每个节点记录了当前节点的数据和下一个节点的引用。相比于数组，在插入和删除数据时，链表具有更好的性能。

下面是一个简单的链表结构定义：

class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
    val = x;
    next = null;
  }
}

实现方法

反转链表的基本思路是从头节点开始，每次将下一个节点插入到当前节点的前面，直到最后一个节点。这个过程可以用迭代或递归的方式实现。

迭代方法

迭代方法的实现比较简单，我们只需要定义两个指针p和q，初始时p指向头节点，q指向p的下一个节点。然后每次将q指向的节点插入到p的前面即可，直到遍历完整个链表。

下面是Java代码实现：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = head;
    ListNode q = head.next;
    while (q != null) {
        ListNode r = q.next;
        q.next = p;
        p = q;
        q = r;
    }
    head.next = null;
    return p;
}

递归方法

递归方法实现方式较为简洁，我们只需要将链表的反转问题转化为前后节点的连接问题。具体实现思路是，先将头节点的下一个节点作为新的头节点，然后将剩余节点的反转问题递归求解。

下面是Java代码实现：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

测试方法

为了验证我们实现的反转链表程序是否正确，我们需要对反转前后的链表进行对比。下面是Java代码实现：

public void testReverseList() {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);

    ListNode newHead = reverseList(head);

    StringBuilder sb = new StringBuilder();
    while (newHead != null) {
        sb.append(newHead.val).append(" -> ");
        newHead = newHead.next;
    }
    String result = sb.toString().substring(0, sb.length() - 4);
    Assert.assertEquals("5 -> 4 -> 3 -> 2 -> 1", result);
}

总结

本篇文章介绍了如何使用Java实现链表的反转，包括迭代和递归两种方法。链表反转是一个常见的编程面试题，在学会了具体的实现方法后，希望能够帮助读者更好地应对面试中的问题。