反转单链表Java实现

问题描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

解题思路

为了实现反转单链表，我们需要记录当前节点（curr），当前节点的前驱节点（prev），当前节点的后继节点（next）。我们还需要一个节点用来记录反转后的头节点（reverseHead）。

1. 初始的时候将curr指向链表的头节点head。prev，next，reverseHead都指向null。
2. curr开始向后循环遍历，遍历结束的条件是curr为null。也就是说我们循环的判断条件应该是while (curr != null)。
3. 在每个循环步骤中
   3.1 将reverseHead指向curr，当遍历结束时，reverseHead指向的就是链表的最后一个节点。
   3.2 将next指向curr.next
   3.3 将curr.next指向prev，反转了
   3.3 将prev指向curr
   3.4 将curr指向next，开始下一轮循环
4. 循环结束，返回reverseHead。

注意：如果解题思路看不懂的话可以直接看代码。

测试用例

1. head 为null
2. 只有一个节点
3. 正常的链表

完整实现

public class Test24 {


    public static class ListNode {

        public int value;
        public ListNode next;
    }

    public static ListNode reverseList(ListNode head) {

        //用于记录反转后的链表的头节点
        ListNode reverseHead = null;
        //用于记录当前处理的节点
        ListNode curr = head;
        //用于记录当前节点的前驱节点
        ListNode prev = null;
        //用于记录当前节点的下一个节点
        ListNode next = null;

        while (curr != null) {
            //记录当前处理的节点，最后一个记录的节点就是反转后的头节点
            reverseHead = curr;
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;

        }
        return reverseHead;

    }

    /**
     * 输出链表的元素值
     *
     * @param head 链表的头节点
     */
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        //test0();
        //test1();
        test2();

    }

    private static void test0() {
        ListNode head = reverseList(null);
        printList(head);
    }

    private static void test1() {
        ListNode head = new ListNode();
        head.value = 1;
        printList(head);
        head = reverseList(head);
        printList(head);
        head = reverseList(head);
        printList(head);
    }

    private static void test2() {
        ListNode head = new ListNode();
        head.value = 1;

        head.next = new ListNode();
        head.next.value = 2;

        head.next.next = new ListNode();
        head.next.next.value = 3;

        head.next.next.next = new ListNode();
        head.next.next.next.value = 4;

        head.next.next.next.next = new ListNode();
        head.next.next.next.next.value = 5;

        head.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.value = 6;

        head.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.value = 7;

        head.next.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.next.value = 8;

        head.next.next.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.next.next.value = 9;

        printList(head);
        head = reverseList(head);
        printList(head);
        head = reverseList(head);
        printList(head);
    }

}

参考链接：

• 【剑指Offer学习】【面试题16 ：反转链表】