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

题目

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

type LinkNode struct {
	value int
	next  *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 := head
	s1 := stack.NewStack()
	for {
		if node != nil {
			s1.Push(node)
			node = node.next
		} else {
			break
		}
	}
	//出栈
	resultHead = s1.Pop().(*LinkNode)
	node2 := resultHead
	for {
		if s1.IsEmpty() {
			//解决环形链表
			node2.next = nil
			break
		}
		temp := s1.Pop().(*LinkNode)
		node2.next = temp
		node2 = node2.next
	}

	return resultHead
}

用例测试

package main

import (
	"fmt"
	"testing"

	"github.com/dengjiawen8955/gostl/ds/stack"
)
type LinkNode struct {
	value int
	next  *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 = node2
	node2.next = node3
	node3.next = node4
	node4.next = node5
	node5.next = node6
	printLink(revLink1(node1))
	// printLink(revLink1(node2))
	// printLink(revLink1(node3))
	// printLink(revLink1(node4))
	// printLink(revLink1(node5))
	// printLink(revLink1(node6))
}


func printLink(head *LinkNode) {
	node := head
	for {
		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 = nil
	return ln
}

func revLink2Recorsion(head *LinkNode) (resultHead, resultNode *LinkNode) {
	if head.next != nil {
		resultHead, resultNode = revLink2Recorsion(head.next)
		resultNode.next = head
		resultNode = resultNode.next
	} else {
		resultHead = head
		resultNode = head
	}
	return
}

解法3 多指针

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

//使用 多指针 反转链表
func revLink3(head *LinkNode) (resultHead *LinkNode) {
	//参数处理
	if head == nil {
		fmt.Printf("%s\n", "err: prams head == nil")
		return nil
	}
	preNode := head
	currentNode := head
	nextNode := head
	count := 1
	for {
		//退出
		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 = nil
	resultHead = nextNode
	return
}