// Type your code here, or load an example.
// Your function name should start with a capital letter.
package main

import "fmt"

// 单链表
// 左移 / 右移 k 位

type Node struct {
    Val  int
    Next *Node
}

func (n *Node) String() string {
    if n == nil {
        return "end"
    }
    return fmt.Sprintf("%d->%s", n.Val, n.Next.String())
}

func NewLinkTable(val []int) *Node {
    if len(val) == 0 {
        return nil
    }
    head := &Node{
        Val: val[0],
    }
    curHead := head
    for i := 1; i < len(val); i++ {
        next := &Node{
            Val: val[i],
        }
        curHead.Next = next
        curHead = next
    }
    return head
}

func main() {
    n := NewLinkTable([]int{1, 2, 3, 4, 5})
    fmt.Printf("table:%s\n", n.String())
    n, _ = RotateLinkTable(n, 2)
    fmt.Printf("table:%s\n", n.String())
    n = NewLinkTable([]int{1, 2, 3, 4, 5})
    n, _ = RotateLinkTable(n, 5)
    fmt.Printf("table:%s\n", n.String())
    n = NewLinkTable([]int{1, 2, 3, 4, 5})
    n, _ = RotateLinkTable(n, 6)
    fmt.Printf("table:%s\n", n.String())
    n = NewLinkTable([]int{1, 2, 3, 4, 5})
    n, _ = RotateLinkTable(n, -2)
    fmt.Printf("table:%s\n", n.String())
    n = NewLinkTable([]int{1, 2, 3, 4, 5})
    n, _ = RotateLinkTable(n, -7)
    fmt.Printf("table:%s\n", n.String())
    n = NewLinkTable([]int{1, 2, 3, 4, 5})
    n.Next.Next.Next = n.Next
    n, err := RotateLinkTable(n, -7)
    fmt.Printf("table:%s\nerr:%s", n.String(), err)
}

// 双指针查环，顺手把长度也求一下
func RotateLinkTable(n *Node, val int) (newHead *Node, err error) {
    if n == nil { // no link table no error
        return nil, nil
    }
    firstPtr := n
    latePtr := n
    step := 0
    for {
        if firstPtr.Next == nil {
            step++
            break
        }
        if firstPtr.Next.Next == nil {
            step += 2
            break
        }
        step += 2
        firstPtr = firstPtr.Next.Next
        latePtr = latePtr.Next
        if firstPtr == latePtr {
            return nil, fmt.Errorf("loop")
        }
    }

    val = val % step
    if val < 0 {
        val += step
    }
    return rotateLintkTableRight(n, val), nil
}

// k 指针
func rotateLintkTableRight(n *Node, val int) (newHead *Node) {
    firstPtr := n
    latePtr := n
    for i := 0; i < val; i++ {
        firstPtr = firstPtr.Next
    }
    for firstPtr.Next != nil {
        firstPtr = firstPtr.Next
        latePtr = latePtr.Next
    }
    firstPtr.Next = n
    newHead = latePtr.Next
    latePtr.Next = nil
    return newHead
}