链表翻转

链表翻转，下面是最简单的一种链表翻转

基本上有两个方法：

• 递归版本
• 非递归版本（多指针）

package main

import "fmt"

type Node struct {
    Element int
    Next    *Node
}

func (n *Node) Generate(num int) {
    tailNode := n
    for i := 0; i < num; i++ {
        node := &Node{Element: i + 1}
        tailNode.Next = node
        tailNode = node
    }
}

//Print 打印
func (n *Node) Print() {
    tailNode := n
    fmt.Println("======print======")
    for tailNode != nil {
        fmt.Printf("ele: %d\n", tailNode.Element)
        tailNode = tailNode.Next
    }
}

//Reverse1 双指针链表翻转
func Reverse1(n *Node) *Node {
    cur := n
    var pre *Node

    for cur != nil {
        tmp := cur.Next
        cur.Next = pre
        pre = cur
        cur = tmp
    }
    return pre
}

//Reverse2 递归翻转
func Reverse2(head, pre *Node) *Node {
    if head == nil {
        return pre
    }

    res := Reverse2(head.Next, head)
    head.Next = pre

    return res
}

//ReverseK 翻转K个链表节点
func ReverseK(head *Node, k int) *Node {

    // 新建一个最前面的Node节点，其下一个节点是待翻转的整个链表的头结点
    headest := &Node{}
    headest.Next = head

    var pre, end *Node
    pre = headest
    end = headest

    for end != nil {

        // 找到K个范围内节点
        for i := 0; i < k && end != nil; i++ {
            end = end.Next
        }

        if end == nil {
            break
        }

        // 要翻转的是[start,end]的闭区间
        // 所以，start要等pre.Next
        start := pre.Next
        // next 则是待翻转区间的头结点
        next := end.Next

        // 断开链表
        end.Next = nil

        pre.Next = Reverse1(start)

        // 将翻转后的子链表与待翻转的链表相连
        start.Next = next

        // 重置变量位置
        pre = start
        end = start
    }

    return headest.Next
}

func main() {
    head := &Node{Element: 0}
    head.Generate(10)

    head.Print()
    head = ReverseK(head, 3)
    head.Print()
    //head = Reverse1(head)
    //head.Print()
    //head = Reverse2(head, nil)
    //head.Print()
}

可以看到Go是真的大道至简呀！！

指针安全，默认零值可以让你少些不少代码。

K个一组翻转链表

其实思路不难，就是在前面翻转整个链表的函数的基础上，我们k个节点，k个节点的找出这个范围来，然后翻转，再链接；

下面这个函数就是在做这个事情。

//ReverseK 翻转K个链表节点
func ReverseK(head *Node, k int) *Node {

    // 新建一个最前面的Node节点，其下一个节点是待翻转的整个链表的头结点
    headest := &Node{}
    headest.Next = head

    var pre, end *Node
    pre = headest
    end = headest

    for end != nil {

        // 找到K个范围内节点
        for i := 0; i < k && end != nil; i++ {
            end = end.Next
        }

        if end == nil {
            break
        }

        // 要翻转的是[start,end]的闭区间
        // 所以，start要等pre.Next
        start := pre.Next
        // next 则是待翻转区间的头结点
        next := end.Next

        // 断开链表
        end.Next = nil

        pre.Next = Reverse1(start)

        // 将翻转后的子链表与待翻转的链表相连
        start.Next = next

        // 重置变量位置
        pre = start
        end = start
    }

    return headest.Next
}