清清楚楚 单链表反转（逆置）

解题考虑

1. 使用额外辅助空间的反转

这样增加了空间复杂度 ，但是实现起来比较容易，不太容易被指针的问题绕晕。
下面给出示例代码

构造链表及初始化

import java.util.Scanner;

/**
 * Created by bruce_shan on 2018/1/10 11:15.
 * Corporation CSU Software  单链表逆置
 */
public class LinkRevert {
     static class  Node
    {
        int data;
        Node next;
    }

    // 插入节点
    static void  insertNode(Node list, Node addNode)
    {
        addNode.next = list.next;
        list.next= addNode;
    }
    // 遍历链表
    static void  printList2(Node list)
    {
        while ((list.next!=null))
        {
            list = list.next;
            System.out.print(list.data + "-->");

        }
        System.out.println();
    }
    // 链表初始化
      static Node init_List()
    {
        Node list = new Node();
        list.next = null;
        Scanner scanner  = new Scanner(System.in);
        int data = scanner.nextInt();
        while (data!=-1)
        {
            Node node = new Node();
            node.data =  data;
            insertNode(list,node);
            data = scanner.nextInt();
        }
        printList2(list);
        return  list;
    }
    public static void main(String[] args) {
        Node list =  init_List();  // 链表初始化
        revert_List(list);
    }
}

解法1：一边遍历原链表一边头插法建新链表

    // 链表逆置  遍历原链表 新建一个链表头插法
    static Node revert_List(Node list)
    {
        Node newList = new Node();
        newList.next = null;
        while ((list.next!=null))
        {
            list = list.next;
            Node temp = new Node();
            temp.data = list.data;
            insertNode(newList,temp);   // 这里插入的节点直接传 list会有问题,会改变原链表
        }
        System.out.println("=====newList== ");
        printList2(newList);
        return newList;
    }

双big O(n) 解法
解法2：借助栈来实现

和解法1类似，这里不给出代码，看官自己实现一下吧。

2. 原地反转

    // 原地链表反转
    static Node revert_List2(Node list)
    {
        Node pRev = new Node();
        pRev.next = null;
        Node pTemp = list.next;
        Node pNext = pTemp;

        while(pNext!= null)
        {
            pNext = pTemp.next;
            pTemp.next = pRev.next;
            pRev.next = pTemp;
            pTemp = pNext;
        }
        printList2(pRev);
        return pRev;
    }

原地反转写法并不复杂，但是要理解清楚，就需要多画画图。

考虑初始状态，将pRev指针建头指针，将pTemp 指向原链表第一个节点（非头节点），pNext 先指向pTemp ，循环体内再指向pTemp下一个节点。

考虑中间状态，时刻记得三个指针分别承担的任务就清楚了。

这道题若还有其他挖掘的地方，欢迎大家交流讨论。