206.反转链表

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

1. 一开始用的头插法进行原地逆置，后来发现他这个题目给的是头指针不是头结点，所以手动new一个头结点ListNode h1=new ListNode(0,head);用头插法时要注意，第一次插入时head.next是等于p的，如果这时候令p.next=head.next会出现环，导致Error - Found cycle in the ListNode错误。因此第一次插入要进行判断：

    if(h1.next!=p)
        p.next=h1.next;
    else
        p.next=null;
   

2. 另一种思路是不动结点，每次仅改变链表中两个结点之间next指向，最终全部都反着指。初始res设置为空,好处在于不用考虑第一个结点(最终变成next为空的最后一个节点)的情况。

1.头插法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node=new ListNode(-1);
        node.next=head;
        if(head==null) return null;
        ListNode p=head,q=head.next;
        p.next=null;
        while(q!=null){
            ListNode temp=q.next;
            q.next=p;
            node.next=q;
            p=q;
            q=temp;
        }
        return node.next;
    }
}

2.原地逆置

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null) return null;
        ListNode p=null,q=head,next=head.next;
        while(q!=null){
            q.next=p;
            p=q;
            q=next;
            if(next==null)break;
            next=next.next;
        }
        return p;
    }
}