LeetCode_双指针_递归_简单_206. 反转链表

x33g5p2x  于2022-05-22 转载在 其他  
字(0.9k)|赞(0)|评价(0)|浏览(301)

1.题目

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

示例 1:

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

示例 2:

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

示例 3:
输入:head = []
输出:[]

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

进阶: 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/reverse-linked-list

2.思路

(1)递归
(2)迭代
思路参考本题官方题解

3.代码实现(Java)

//思路1————递归
public ListNode reverseList(ListNode head) {
	//递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    /*
    	head->head1->null
		经过 head.next.next = head 之后,得到 head1->head->head1
		经过 head.next = null 之后,得到 head1->head->null
		这样便将 head 与 head1 进行了反转
	*/
    head.next.next = head;
    head.next = null;
    return newHead;
}
//思路2————迭代
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
    	//使用 next 记录当前节点 cur 的下一个节点
        ListNode next = cur.next;
        //将当前节点 cur 的下一个节点指向 prev
        cur.next = prev;
        //cur 和 prev 均向后移动
        prev = cur;
        cur = next;
    }
    return prev;
}

相关文章