java实现单链表之逆序

Java实现单链表之逆序

数据结构

单链表是一种经典的数据结构，它是由一组节点组成，每个节点包含两部分，一是保存数据的部分，二是指向下一个节点的地址。单链表只能从前往后遍历，无法从后往前遍历。

逆序算法实现

迭代法

在迭代法中，我们需要先定义三个指针，分别为当前节点p、其前驱节点prev和其后继节点next。

1. 首先让p指向当前链表的第一个节点，prev和next都为空。
2. 当p不为空时，将next指向p的下一个节点。
3. 将p的next指向prev，实现节点的逆序。
4. 将prev指针指向p，p指针指向next，即向后移动。
5. 反复执行以上操作，直到p指向链表的尾节点时，逆序完成。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode next = null;
    ListNode p = head;
    while (p != null) {
        next = p.next;
        p.next = prev;
        prev = p;
        p = next;
    }
    return prev;
}

递归法

在递归法中，我们需要先定义递归函数和边界条件。

1. 定义递归函数，该函数的参数为当前节点，函数的返回值为逆序后的链表头。
2. 定义边界条件，当节点为空或节点已经是链表尾节点时，返回当前节点。

在递归函数的实现中，我们需要按照逆序的顺序依次递归每个节点，并将当前节点的下一个节点指向自己，实现节点的逆序。

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

示例

假设现在有一个单链表，如下所示：

1 -> 2 -> 3 -> 4 -> 5 -> null

使用迭代法进行逆序操作后，链表变为：

5 -> 4 -> 3 -> 2 -> 1 -> null

使用递归法进行逆序操作后，链表变为：

5 -> 4 -> 3 -> 2 -> 1 -> null

总结

单链表的逆序操作可以使用迭代法和递归法两种方法实现，二者的时间和空间复杂度不尽相同，实际使用中需要根据具体情况选择合适的方法。