算法通关村第二关-青铜终于学会链表了

大家好我是苏麟 , 今天来学反转链表 . 

反转链表

描述 :

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

LeetCode 206.反转链表 : 

206. 反转链表

牛客 BM1 反转链表 :

 分析 : 

本题有两种方法，带头结点和不带头结点，我们都应该会，因为这两种方式都很重要，如果搞清楚，很多链表的算法题就不用做了。

当然也可以用栈 , 这样也很简单 . 

建立虚拟头结点辅助反转

前面分析链表插入元素的时候，会发现如何处理头结点是个比较麻烦的问题，为此可以先建立一个虚拟的结点ans，并且令ans.next=head，这样可以很好的简化我们的操作。如下图所示，如果我们将链表(1->2>3->4->5进行反转，我们首先建立虚拟结点ans，并令ans.next=node(1)，接下来我们每次从旧的链表拆下来一个结点接到ans后面，然后将其他线调整好就可以了。

import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        ListNode node = new ListNode(0);
        ListNode p = head;
        while(p != null){
            ListNode s = head.next;
            s.val = p.val;
            node.next = s;
            p = p.next;
        }
        return node;
    }
}

建立虚拟结点是处理链表的经典方法之一，虚拟结点在很多工具的源码里都有使用，用来处理链表反转也比较好理解，因此我们必须掌握好。

直接操作链表实现反转

上面的方式虽然好理解应用也广，但是可能会被面试官禁止，为啥?原因是不借助虚拟结点的方式更难更能考察面试者的能力。
我们观察一下反转前后的结构和指针位置:

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

理解这个图就够了，直接看代码:

import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

将上面这段代码在理解的基础上背下来，是的，因为这个算法太重要!!!

这期就到这里 , 下期见!