给你单链表的头节点 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
/** * 思路: * 设置前驱节点pre * 反转:让current指向pre * 不断的移动pre和current,直到current==null * 返回pre */ public static ListNode reverseList(ListNode head) { ListNode pre = null; ListNode curr = head; while (curr!=null){ ListNode next = curr.next; curr.next=pre; pre=curr; curr=next; } return pre; }
时间复杂度:On
空间复杂度:O1
/** * 思路: * 头节点指向nn * 反转:next指向curr * 循环直到next节点指向null * 返回curr */ public static ListNode reverseList(ListNode head) { if (head==null){ return head; } ListNode curr = head; ListNode next = curr.next; while (next!=null){ ListNode nn = next.next; next.next=curr; head.next=nn; curr=next; next=nn; } return curr; }
时间复杂度:On
空间复杂度:O1
/** * 思路: * 递归到尾节点 * 反转相邻节点:后面的节点指向当前节点,当前节点指向null * 返回尾节点 */ public static ListNode reverseList(ListNode head) { return recursive(head); } private static ListNode recursive(ListNode head) { if (head==null||head.next==null){ return head; } //tail是最后结果的头指针 ListNode tail=recursive(head.next); head.next.next=head; head.next=null; return tail; }
时间复杂度:On
空间复杂度:On