12-反转链表算法

反转链表的基本思路是：从头结点开始遍历链表，每次将当前节点的 next 指针指向前一个节点，然后将前一个节点设置为当前节点，最后将当前节点设置为原来的下一个节点。当遍历完成时，链表的头节点即为原来的尾节点，整个链表也就被反转了过来。

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

class ReverseLinkedList {
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

验证：

public class Test {
    public static void main(String[] args) {
        // 创建链表 1 -> 2 -> 3 -> 4 -> 5
        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);
        printVal(head, 5); //1 2 3 4 5

        // 反转链表
        ListNode newHead = ReverseLinkedList.reverseList(head);
        printVal(newHead, 5); //5 4 3 2 1
    }

    public static void printVal(ListNode listNode, int len) {
        for (int i = 0; i < len; i++) {
            System.out.println("listNode.val = " + listNode.val);
            listNode = listNode.next;
        }
    }
}

首先创建了一个链表 1 -> 2 -> 3 -> 4 -> 5，然后调用 ReverseLinkedList.reverseList() 方法来反转链表。最后，我们通过遍历反转后的链表，并与预期结果进行比较，来验证反转链表的正确性。