反转链表

发表于 | 分类于 |
字数统计: 724 字 | 阅读时长 ≈ 3 分钟

题目描述：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例 ：

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

限制：0 <= 节点个数 <= 5000

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode reverseList(ListNode head) {

  }
}

方法一：双指针迭代

设置两个指针，不断修改当前节点的 next ，例如 cur.next = pre

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
  public ListNode reverseList(ListNode head) {
    // 申请节点，pre、cur、temp，cur 指向 head，pre、temp指向null
    ListNode pre = null, cur = head, temp = null;
    while(cur != null) {
      // 记录当前节点的下一个节点
      temp = cur.next;
      // 然后将当前节点指向pre
      cur.next = pre;
      // pre和cur节点都前进一位
      pre = cur;
      cur = temp;
    }
    return pre;
  }
}

复杂性分析：

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：39.4 MB, 在所有 Java 提交中击败了73.62%的用户

方法二：递归

首先需要设置递归终止条件，开始递归，从最后的节点开始修改 next

递归.gif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public ListNode reverseList(ListNode head) {
    //递归终止条件：当前为空，或者下一个节点为空
    if(head == null || head.next == null) {
      return head;
    }
    // 这里的cur就是最后一个节点
    ListNode cur = reverseList(head.next);
    // 这里请配合动画演示理解
    // 如果链表是 1->2->3->4->5，那么此时的cur就是5
    // 而head是4，head的下一个是5，下下一个是空
    // 所以head.next.next 就是5->4
    head.next.next = head;
    // 防止链表循环，需要将head.next设置为空
    head.next = null;
    // 每层递归函数都返回cur，也就是最后一个节点
    return cur;
  }
}

复杂性分析：

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：39.6 MB, 在所有 Java 提交中击败了44.56%的用户

方法三：栈

利用栈先进后出的特点，把节点推进栈，再一个个弹出来，需要注意的是，弹出来后的节点需要更改它们的next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public ListNode reverseList(ListNode head) {
    if(head == null || head.next ==null) return head;
    Deque<ListNode> stack = new LinkedList<>();
    while(head != null) {
      stack.push(head);
      head = head.next;
    }
    head = stack.pop();
    ListNode cur = head;
    while(!stack.isEmpty()) {
      ListNode node = stack.pop();
      node.next = null;
      cur.next = node;
      cur = node;
    }
    return head;
  }
}

复杂性分析：

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：39.4 MB, 在所有 Java 提交中击败了83.03%的用户