算法通关村第二关——终于学会链表反转了

Leetcode 206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

解析：

方法1：建立虚拟头节点辅助反转

首先建立一个虚拟的结点ans，并且令ans.next=head，这样可以很好的简化我们的操作。如下图所示，如果我们将链表(1->2>3->4->5进行反转，我们首先建立虚拟结点ans，并令ansnext=node(1)，接下来我们每次从旧的链表拆下来一个结点接到ans后面，然后将其他线调整好就可以了。

如上图所示，我们完成最后一步之后，只要返回ans.next就得到反转的链表了，代码如下：

/**
     * 方法1：虚拟结点，,并复用已有的结点
     *
     * @param head ListNode
     * @return ListNode
     */
    public static ListNode reverseListByDummyNotCreate(ListNode head) {
        ListNode ans = new ListNode(-1);
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        return ans.next;
    }

方法2：直接操作链表实现反转

首先观察一下反转前后的结构和指针位置：

再看一下执行期间的过程示意图，在图中，cur本来指向旧链表的首结点，pre表示已经调整好的新链表的表头，next是下一个要调整的。注意图中箭头方向，cur和pre是两个表的表头，移动过程中cur经过一次中间状态之后，又重新变成了两个链表的表头。

代码如下：

/**
     * 方法3：不适用头结点，基本的反转方法
     *
     * @param head ListNode
     * @return ListNode
     */
    public static ListNode reverseListSimple(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

方法3：递归实现链表反转

链表反转的两种方法，带虚拟头结点方法是很多底层源码使用的，而不使用带头结点的方法是面试经常要考的。

链表反转还有第三种常见的方式，使用递归来实现：

/**
     * 方法3：通过递归实现链表反转
     *
     * @param head ListNode
     * @return ListNode
     */
    public static ListNode reverseListByRecurse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseListByRecurse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

首先检查链表是否为空或只有一个节点，如果是，则直接返回头节点。否则，它递归地反转剩余的链表，并将头节点的下一个节点的下一个节点设置为头节点，然后将头节点的下一个节点设置为null，以防止链表循环。最后，它返回新的头节点，即原链表的末尾节点。