反转链表

题目链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

image.png

思路解题
我们反转链表，只需要记录前一个node为pre，然后在当前node指向它即可。

代码如下

public class ListNode {

        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。