算法通关村第二关|青铜|链表反转

1.建立虚拟头结点辅助反转

1.1 反转链表：使用虚拟头结点辅助反转。

public ListNode reverseList(ListNode head) {
	ListNode ans = new ListNode(0);
	ListNode cur = head;
	while (cur != null) {
        ListNode next = cur.next;
        cur.next = ans.next;
        ans.next = cur;
        cur = next;
    }
	return ans.next;
}
1
2
3
4
5
6
7
8
9
10
11

2.直接操作链表实现反转

2.1 反转链表：使用迭代。

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;
}
1
2
3
4
5
6
7
8
9
10
11

2.2 反转链表：使用递归。

public ListNode reverseList(ListNode head) {
	if (head == null || head.next == null) {
        return head;
	}
    ListNode newHead = reverseList(head.next);
	head.next.next = head;
	head.next = null;
	return newHead;
}
1
2
3
4
5
6
7
8
9

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤