反转链表（牛客网）

注意点：空间复杂度为(1)，就是说只能原地反转

自己的代码：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
           if(head==null) return null;
           //在最后一个结点处将前面所有结点进行头插法
           //1.先找到最有一个结点
           ListNode newH=head;
           while(newH.next!=null){
               newH=newH.next;
           }
           //2.将前面所有的节点在newH后进行头插法
           ListNode p=head,r;
           while(p!=newH){
               //头插法
               r=p.next;//
               p.next=newH.next;
               newH.next=p;
               p=r;
           }
           return newH;
    }
}

讨论区里更简洁的代码：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
           ListNode pre=null;
           ListNode curr=head;
           while(curr!=null){
               ListNode next=curr.next;
               curr.next=pre;
               pre=curr;
               curr=next;
           }
        return pre;
    }
}

思路：第一个元素相当于最后一个元素，在遍历过程中不断将指针进行翻转，遍历到最后一个元素即为反转后的第一个元素