[算法]剑指offer p16 反转链表 golang

题目

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。链表结点定义如下：

type LinkNode struct {value intnext  *LinkNode
}

解法1: stack

问下面试官是否可以有分配的空间, 如果有的话我们可以用栈来实现十分简单

• 遍历链表并 Push 栈
• Pop栈重构链表

代码

// 5, 6
//使用 stack 反转链表
func revLink1(head *LinkNode) (resultHead *LinkNode) {//参数处理if head == nil {fmt.Printf("%s\n", "err: param  head == nil ")return nil}//push栈node := heads1 := stack.NewStack()for {if node != nil {s1.Push(node)node = node.next} else {break}}//出栈resultHead = s1.Pop().(*LinkNode)node2 := resultHeadfor {if s1.IsEmpty() {//解决环形链表node2.next = nilbreak}temp := s1.Pop().(*LinkNode)node2.next = tempnode2 = node2.next}return resultHead
}

用例测试

package mainimport ("fmt""testing""github.com/dengjiawen8955/gostl/ds/stack"
)
type LinkNode struct {value intnext  *LinkNode
}
func TestP16(t *testing.T) {node1 := &LinkNode{value: 1, next: nil}node2 := &LinkNode{value: 2, next: nil}node3 := &LinkNode{value: 3, next: nil}node4 := &LinkNode{value: 4, next: nil}node5 := &LinkNode{value: 5, next: nil}node6 := &LinkNode{value: 6, next: nil}node1.next = node2node2.next = node3node3.next = node4node4.next = node5node5.next = node6printLink(revLink1(node1))// printLink(revLink1(node2))// printLink(revLink1(node3))// printLink(revLink1(node4))// printLink(revLink1(node5))// printLink(revLink1(node6))
}func printLink(head *LinkNode) {node := headfor {if node != nil {fmt.Printf("%d->", node.value)node = node.next} else {break}time.Sleep(time.Millisecond * 100)}fmt.Printf("%s\n", "")
}

解法2: 递归

stack 栈的本质就是递归, 下面我们也能通过递归实现上面的代码

//使用 递归 反转链表
func revLink2(head *LinkNode) (resultHead *LinkNode) {//参数处理if head == nil {fmt.Printf("%s\n", "err: prams head == nil")return nil}ln, ln2 := revLink2Recorsion(head)ln2.next = nilreturn ln
}func revLink2Recorsion(head *LinkNode) (resultHead, resultNode *LinkNode) {if head.next != nil {resultHead, resultNode = revLink2Recorsion(head.next)resultNode.next = headresultNode = resultNode.next} else {resultHead = headresultNode = head}return
}

解法3 多指针

如果面试官要求不能使用额外的储存(递归也算是), 我们就必须在循环中解决, 用多指针来控制链表的反转

//使用 多指针 反转链表
func revLink3(head *LinkNode) (resultHead *LinkNode) {//参数处理if head == nil {fmt.Printf("%s\n", "err: prams head == nil")return nil}preNode := headcurrentNode := headnextNode := headcount := 1for {//退出if nextNode.next == nil {break}count++if count > 3 {preNode = currentNode}if count > 2 {currentNode = nextNode}//移动nextNode = nextNode.next//反转节点currentNode.next = preNode}//链接最后一个节点nextNode.next = currentNode//防止环形链表head.next = nilresultHead = nextNodereturn
}