力扣hot100 反转链表 指针 递归 一题多解

Problem: 206. 反转链表

思路

👨?🏫 大佬题解

💖 迭代 + 双指针

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(1)$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
	public ListNode reverseList(ListNode head)
	{
        if (head == null)
			return head;
		ListNode pre = null;//前驱节点
		ListNode cur = head;//当前节点
		while (cur != null)//遍历到 null 说明遍历完了
		{
			ListNode tmp = cur.next;// tmp 保存后继节点即可
			cur.next = pre;
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
}

💖 递归

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
//	递归
	public ListNode reverseList(ListNode head)
	{
		return recur(head, null);
	}

	/**	使得 cur 指向 pre
	 * @param head 当前节点
	 * @param object 当前节点的前驱节点
	 * @return 返回反转后的头结点 
	 */
	private ListNode recur(ListNode cur, ListNode pre)
	{
		if(cur == null)
			return pre;
		ListNode res = recur(cur.next, cur);
		cur.next = pre;
		return res;
	}
}