当前位置：首页 > news >正文

【力扣打卡系列】反转链表

news 2025/1/10 11:22:24

坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day12

反转链表

题目描述

在这里插入图片描述

解题思路
- 最开始的头节点为空，可以赋值为nil
- 从前往后依次逆转下一个节点的指向即可
代码参考

/*** 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
}

tips
- 当前第一个节点指向的是头节点head
- 注意需要单开一个next节点来存储当前节点原来的next值
- 循环条件为cur != nil，不能省略为cur，因为不是布尔类型的值
- 最后返回当前最后一个节点（pre），也就是新链表的头节点

反转链表2

题目描述

在这里插入图片描述

解题思路
- 首先初始化哨兵节点
- P0：指向开始被反转的节点的前一个未反转的节点的指针
- right-left+1是被反转的节点个数
- 最终p0指向下一个节点是已经反转的最后一个节点pre,即反转链表的头节点
- 原先p0指向下一个节点指向cur
代码参考

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {guard := &ListNode{Next:head}p0 := guardfor i:=0;i<(left-1);i++{p0 = p0.Next}cur := p0.Nextvar pre *ListNodepre = nilfor i:=0;i<(right-left+1);i++{next := cur.Nextcur.Next = prepre = curcur = next}p0.Next.Next = curp0.Next = prereturn guard.Next
}

tips
- 性质：反转结束后，从原来的链表来看
- pre指向反转这一段的末尾
- cur指向反转这一段后续的下一个节点
- 特殊情况：left等于1的时候没有p0
- 解决：在前面加一个哨兵节点，这样p0就存在了
- 注意哨兵节点的声明：guard := &ListNode{Next:head}，不能先Var再赋值next
- 注意指定次数的for循环的写法： for i:=0;i<(right-left+1);I++
- 注意pre的声明及初值，要放在逆转循环体的外面：
  - var pre *ListNode
    pre = nil
- 注意最后这里勿漏next：
  - p0.Next.Next = cur
    p0.Next = pre
- 为什么最终返回guard.Next：因为当left=1时，原先的head就被反转了，所以不能返回head

k个一组翻转链表

题目描述
解题思路
- 先拿到链表长度，求出有多少组k
- 求链表长度n
  - for cur != nil{
    cur = cur.Next
    n++
    }
- 中间记得保存一下p0.Next的值
代码参考

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func reverseKGroup(head *ListNode, k int) *ListNode {n := 0guard := &ListNode{Next:head}p0 := guardcur := headfor cur != nil{cur = cur.Nextn++}cur = p0.Nextvar pre *ListNodepre = nilfor num := n/k;num != 0;num--{for i:=0;i<k;i++{nxt := cur.Nextcur.Next = prepre = curcur = nxt}nxt_p0 := p0.Nextp0.Next.Next = curp0.Next = prep0 = nxt_p0}return guard.Next
}