题目:

206. 反转链表

题解:

1. 迭代法:

双指针迭代
我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。
第二个指针 cur 指向 head,然后不断遍历 cur。
每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。

动画演示如下:

2. 递归法:

这题有个很骚气的递归解法,递归解法很不好理解,这里最好配合代码和动画一起理解。
递归的两个条件:

  • 终止条件是当前节点或者下一个节点==null
  • 在函数内部,改变节点的指向,也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head

很不好理解,其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点,在递归函数内部,改变的是当前节点的指向。

动画演示如下:

代码:

1. 代码一:(参考迭代法)

/** * code206 */
public class code206 {

    public static ListNode reverseList(ListNode head) {
        // 申请节点,pre和 cur,pre指向null
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null) {
            // 记录当前节点的下一个节点
            tmp = cur.next;
            // 然后将当前节点指向pre
            cur.next = pre;
            // pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public static void print(ListNode node) {
        if (node == null) {
            return;
        }
        ListNode current = node;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode head = reverseList(listNode1);
        print(head);
    }
}

2. 代码二:(参考递归法)

/** * code206 */
public class code206 {

    // 递归法
    public static ListNode reverseList(ListNode head) {
        // 递归终止条件是当前为空,或者下一个节点为空
        if (head == null || head.next == null) {
            return head;
        }
        // 这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        // 这里请配合动画演示理解
        // 如果链表是 1->2->3->4->5,那么此时的cur就是5
        // 而head是4,head的下一个是5,下下一个是空
        // 所以需要head.next.next == head, 就是5->4
        head.next.next = head;
        // 防止链表循环,需要将head.next设置为空。如果使用大小为 2 的链表测试代码,则可能会捕获此错误。
        head.next = null;
        // 每层递归函数都返回cur,也就是最后一个节点
        return cur;
    }

    public static void print(ListNode node) {
        if (node == null) {
            return;
        }
        ListNode current = node;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode head = reverseList(listNode1);
        print(head);
    }
}

参考:

  1. 动画演示+多种解法 206. 反转链表
  2. 反转链表
  3. 帮助大家理解递归做法