记一次逆转链表 - Githubissues

字节面试时做的，不难，但是现场无IDE确实是很难做对。当时调到一般发现怎么都过不了牛客网的编译器…… 题目是这样子的：对于给定的链表：1->2->3->4->5->6->7, 给定一个m，要求每隔这个间隔进行一次翻转 m = 2, 2->1->4->3->6->5->7 m= 3, 3->2->1->6->5->4->7

这道题的难点在于手跑代码和边界条件，肯定是有更好的，这个只是我事后花了半个小时快速写的。当时面试的时候没跑出来，怎么都过不了编译，后面发现是结构体中Ndoe的位置放反了……脑子抽了。不过就算过了编译也很难做对，没有纸笔的情况下这个边界条件比较飞天

逻辑大致如下：逆转指针

package main

import "fmt"

type Node struct {
    Val int
    Next *Node
}

type List struct{
    Head *Node
    Tail *Node
}

func search(l List){
    pointer := l.Head
    for pointer!=nil{
        fmt.Printf("%d ",pointer.Val)
        pointer = pointer.Next
    }
    fmt.Printf("\n")
}

func insert(l *List,node *Node){
    l.Tail.Next = node
    l.Tail = node
}

func main() {
    head := &Node{Val:1,Next:nil}
    l := List{Head:head,Tail:head}
    n:=7

    for i:=2;i<=n;i++{
        insert(&l,&Node{Val:i,Next:nil})
    }

    m:=2
    pointer := l.Head
    pointerHead := l.Head
    var pointerPrevious *Node = nil
    var cacheHead *Node
    var cacheTail *Node
    setHead := false
    for i:=1;i<=n;{
        if pointerPrevious == nil{
            cacheHead = nil // cacheHead = 1
            cacheTail = nil // cacheTail = 1
        }else{
            cacheHead = pointer // cacheHead = 3
            cacheTail = pointer // cacheTail = 3
        }

        fmt.Println(i)
        if i+m > n{
            break
        }
        for j:=0;j<m; i,j = i+1,j+1{
            // cacheHead = 4
            // cacheTail = 3
            // pointer = 4
            // pointerHead = 5
            pointerHead = pointer // 4
            pointer = pointer.Next // 5

            pointerHead.Next = cacheHead // 4->next = 3
            cacheHead =  pointerHead // cacheHead = 4
            if cacheTail == nil{
                cacheTail = cacheHead //
            }
        }
        cacheTail.Next = pointer // 3->next = 5
        if !setHead{
            l.Head = cacheHead
            setHead = true
        }else{
            pointerPrevious.Next = cacheHead // 1->next = 4
        }
        pointerPrevious = cacheTail
    }

    search(l)
}

wtysos11 / blogWiki

记一次逆转链表 #223