给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
迭代:定义节点,然后不断迭代改变箭头方向最后返回
class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } }
时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
空间复杂度:O(1)。
递归:不好理解
class Solution { 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; } }
时间复杂度:O(n),其中 n 是链表的长度。需要对链表的每个节点进行反转 *** 作。
空间复杂度:O(n),其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间,最多为 n 层。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)