• 206. 反转链表

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

    示例 1：

    1
    2
    输入：head = [1,2,3,4,5]
    输出：[5,4,3,2,1]

    示例 2：

    1
    2
    输入：head = [1,2]
    输出：[2,1]

    示例 3：

    1
    2
    输入：head = []
    输出：[]

    提示：

    • 链表中节点的数目范围是 [0, 5000]
    • -5000 <= Node.val <= 5000

题解：

双指针迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode reverseList(ListNode head) {

    ListNode pre = null;
    ListNode cur = head;
    //用于保存反转的下一节点
    ListNode temp = null;

    while (cur != null) {
        //保存下一节点
        temp = cur.next;
        //反转操作
        cur.next = pre;
        //更新指针
        pre = cur;
        cur = temp;
    }
    //最终cur指向null，pre指向链表头部
    return pre;
}
  • 时间复杂度:O(N)
  • 空间复杂度:O(1)