反转链表

头插法:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode(0);newHead.next = null;
        ListNode p = head;
        ListNode q;
        while(p!=null){
            q=p;
            p = p.next;
            q.next = newHead.next;
            newHead.next = q;
        }

        return newHead.next;
    }
}

就地逆转

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;

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

        return pre;
    }
}