Offer.P24[反转链表]

方法一：迭代(双指针)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode cur, ListNode pre) {
        if (cur == null) return pre;
        // 递归后继节点,递归终止后返回的节点为链表最后一个节点(即反转链表的头结点)
        ListNode head = reverse(cur.next, cur);
        // 修改节点引用指向
        cur.next = pre;
        // 返回反转链表头结点
        return head;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$