翻转单链表

• 在有关链表的题目中，最需要注意的地方就是各个结点引用的调整，否则很容易因为混乱的指向导致死循环等情况。
• 技巧：定义引用指向（保存）某个结点，防止由于调整链表结构，导致某些结点丢失。
• 对于翻转单链表一般有两种做法：
  • 1、逐个翻转，保存当前结点的前一个结点，然后调整指向。
  • 2、不断的将后面的链表丢到头节点的后面，然后将头节点丢到最后面。

方法一：

    /**
     * 方法一：逐个翻转
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        if (head == null)
            return null;

        ListNode pre = null;
        ListNode cur = head;
        while (cur != null)
        {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }

方法二：

    //方法二：不断选择后一个结点，插入到头节点后面
    public static ListNode re(ListNode head) {
        if (head == null) return null;

        if (head.next == null)
            return head;

        if (head.next.next == null){
            ListNode n = head.next;
            head.next = null;
            n.next = head;
            return n;
        }

        ListNode cur = head.next.next;
        ListNode pre = head.next;
        while (cur != null){
            //临时结点，存放当前结点的下一个结点
            ListNode temp = cur.next;
            //将cur的前一个结点指向cur的下一个结点
            pre.next = temp;
            //解除cur.next的先前指向，重定向为head下一个结点。
            cur.next = head.next;
            //解除head的先前指向，重定向为cur
            head.next = cur;
            //调整引用，cur向后一位
            cur = temp;
        }

        //添加引用到头节点的下一个结点，即翻转链表后的新头结点。
        ListNode newNode = head.next;
        //移动头节点到尾部
        pre.next = head;
        //解除下一个指向的引用，避免死循环
        head.next = null;
        return newNode;
    }

https://github.com/yuanoOo/Algorithm/tree/master/Linked%20List