扬中网站,怎样制作网站?,南海最新消息,山西省住房和城乡建设厅网站报名给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a;
输入#xff1a;head [1,2,3,4,5] 输出#xff1a;[5,4,3,2,1] 示例 2#xff1a;
输入#xff1a;head [1,2] 输出#xff1a;[2,1] 示例 3#xff1a;
…给你单链表的头节点 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
进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
法一迭代法遍历整个链表每遍历到一个节点让它指向前驱节点
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func reverseList(head *ListNode) *ListNode {var pre *ListNode nilcur : headfor cur ! nil {next : cur.Nextcur.Next prepre curcur next}return pre
}如果链表中有n个节点此算法时间复杂度为O(n)空间复杂度为O(1)。
法二递归法每递归到一个节点令其下一节点指向自身然后令自身的下一节点指向空为了头节点的下一节点指向空反正本次递归返回后上层节点非nil时上层递归会修改本节点的Next值。每次递归我们都返回链表的最后一个节点
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func reverseList(head *ListNode) *ListNode {if head nil || head.Next nil {return head}ans : reverseList(head.Next)head.Next.Next headhead.Next nilreturn ans
}如果链表中有n个节点此算法时间复杂度为O(n)空间复杂度为O(n)。
