Problem: 206. 反转链表

思路

👨‍🏫 大佬题解

💖 迭代 + 双指针

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

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode h = null;//翻转链表的头结点
        //遍历节点，每遍历到一个节点就把当前节点放在已经翻转的链表头部 cur.next = pre;
        while(cur != null)
        {
            ListNode next = cur.next; // 保存后续节点
            cur.next = h; //头插法实现翻转链表
            h = cur;//头结点改为当前节点
            cur = next;//继续遍历后续节点
        }
        return h;
    }
}

💖 递归

⏰ 时间复杂度: $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;
	}
}