题目链接

力扣——反转链表

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路

1. 前置双指针迭代

利用一个前置指针 pre = null ，将 head.next 指向 pre，就相当于完成一个局部的反转，后面的节点做同样的过程即可。需要注意的是：在更改 head.next 前使用一个变量 temp 来保存 head 的下一个节点，以便完成后续操作。

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

复杂度分析：

• 时间复杂度：#card=math&code=O%28N%29&id=Arr9o)，遍历整个链表，N 取决于链表节点个数。

• 空间复杂度：#card=math&code=O%281%29&id=t8b8i)

  2. 原地双指针迭代

  public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    while (head != null && head.next != null) {
        ListNode temp = head.next.next;
        head.next.next = cur;
        cur = head.next;
        head.next = temp;
    }
    return cur;
  }
  

  复杂度分析：

• 时间复杂度：#card=math&code=O%28N%29&id=cWWTb)，遍历整个链表，N 取决于链表节点个数。

• 空间复杂度：#card=math&code=O%281%29&id=vatdA)

  3. 递归

  public ListNode reverseList(ListNode head) {
    // 递归出口
    if (head == null || head.next == null) {
        return head;
    }
    ListNode ret = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return ret;
  }
  

  复杂度分析：

• 时间复杂度：#card=math&code=O%28N%29&id=dEwup)，遍历整个链表，N 取决于链表节点个数。

• 空间复杂度：，递归调用系统栈，N 取决于链表节点个数。