零食电子商务网站建设策划书,昆山市建设局网站,玉环做网站,wordpress 建博客教程文章目录 翻转链表 leetcode206题解第一版 直接建立新的链表双指针迭代递归法 翻转链表 leetcode206
至此走到这里#xff0c;我们对于链表的结构应当已经比较熟悉#xff0c;下面的就是敢于操作
题解第一版 直接建立新的链表
时间复杂度太高
// 初始方法#xff0c;建立… 文章目录 翻转链表 leetcode206题解第一版 直接建立新的链表双指针迭代递归法 翻转链表 leetcode206
至此走到这里我们对于链表的结构应当已经比较熟悉下面的就是敢于操作
题解第一版 直接建立新的链表
时间复杂度太高
// 初始方法建立新链表
func reverseList(head *ListNode) *ListNode {NewNode : ListNode{}for ; head ! nil; head head.Next {NewNode.Val head.ValNewNode ListNode{Next: NewNode}}return NewNode.Next
}
双指针迭代
其实在初始时也曾考虑过最后没有直面的勇气抽自己两个大嘴巴子必须醒悟fuckmyself 当时卡在觉得修改顺序会将链表后面的一大串也甩过来现在发现多虑了
// 迭代 双指针法
func reverseList(head *ListNode) *ListNode {如果原链表为空或者nil直接返回原链表//if head nil || head.Next nil {// return head//}// 0 1 2 3 4cur : head//pre : ListNode{}var pre *ListNode //这样定义不分配内存在后续第一次向外赋值即为nil而上面的定义则会为0//结果后续函数可以覆盖前面的特殊情况 for cur ! nil {c : cur.Nextcur.Next prepre curcur c}return pre}
递归法
链表的操作需要记住三个东西上一个是谁我是谁下一个是谁。
用递归帮忙记住了上一个是谁那么问题是我是谁下一个是谁第一行的if判断是两种临界情况第一种是头结点为空不用管第二种是没有下一个了只用知道我是谁直接返回就行。下面的几行代码我明显是head下一个就是head-next由于要反转链表我的下一个要变成我的上一个因此head-next-next head我的上一个递归等到这层递归出去再解决。可以看到newHead在递归结束返回后是没有进行任何操作的也就是返回的是最底层的那个起到传递尾新首结点的作用
// 递归也为双指针
// 把自己和后面的换
func reverseList(head *ListNode) *ListNode {//递归结束条件if head nil || head.Next nil {return head}//调用自身newHead : reverseList(head.Next)//处理递归//由于翻转链表那么我们的目的就是目前节点的下一个改为上一个//目前节点head.nexthead.Next.Next head//上面这么写会使链表成环这里要打破 环head.Next nilreturn newHead
}
