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

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

反转链表

题目描述

在这里插入图片描述

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode= nil
    cur := head
    for cur != nil{
        next :=cur.Next
        cur.Next = pre
        pre = cur
        cur =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 := guard
    for i:=0;i<(left-1);i++{
        p0 = p0.Next
    }
    cur := p0.Next
    var pre *ListNode
    pre = nil
    for i:=0;i<(right-left+1);i++{
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    p0.Next.Next = cur
    p0.Next = pre
    return 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 := 0
    guard := &ListNode{Next:head}
    p0 := guard
    cur := head
    for cur != nil{
        cur = cur.Next
        n++
    }
    cur = p0.Next
    var pre *ListNode
    pre = nil
    for num := n/k;num != 0;num--{
        for i:=0;i<k;i++{
            nxt := cur.Next
            cur.Next = pre
            pre = cur
            cur = nxt
        }
        nxt_p0 := p0.Next
        p0.Next.Next = cur
        p0.Next = pre
        p0 = nxt_p0
    }
    return guard.Next
}