s = s * 10 + a%10
a = a/10
2.字符串判断回文
package main
//思路： 开发一个栈来来存放链表的上半段
func isPalindrome1(l *LinkedList) bool {
lLen := l.length
if lLen == 0 {
return false
}
if lLen == 1 {
return true
}
s := make([]string, 0, lLen/2)
cur := l.head
for i := uint(1); i <= lLen; i++ {
cur = cur.next
if lLen % 2 != 0 && i == (lLen/2 + 1) {
continue
}
//有一半入栈
if i <= lLen/2 {
s = append(s,cur.GetValue().(string))
} else {
//后一半和前一半做对比
if s[lLen - i] != cur.GetValue().(string) {
return false
}
}
}
return true
}
//思路： 找到链表中间节点，将前半部分转置，在从中间向左右遍历对比
func isPalindrome2(l *LinkedList) bool {
lLen := l.length
if lLen == 0 {
return false
}
if lLen == 1 {
return true
}
var isPalindrome = true
step := lLen/2
var pre *ListNode = nil
cur := l.head.next
next := l.head.next.next
for i := uint(1); i <= step; i++ {
tmp := cur.GetNext()
cur.next = pre
pre = cur
cur = tmp
next = cur.GetNext()
}
mid := cur
var left,right *ListNode = pre,nil
if lLen%2 != 0 {
right = mid.GetNext()
} else {
right = mid
}
for nil != left && nil != right {
if left.GetValue().(string) != right.GetValue().(string) {
isPalindrome = false
break
}
left = left.GetNext()
right = right.GetNext()
}
cur = pre
pre = mid
for nil != cur {
next = cur.GetNext()
cur.next = pre
pre = cur
cur = next
}
l.head.next = pre
return isPalindrome
}
//test
package main
import "testing"
func TestPalindrome1(t *testing.T){
strs := []string{"heooeh","hello","heooeh","a",""}
for _,str1 := range strs {
l := NewLinkedList()
for _,c := range str1 {
l.InsertToTail(string(c))
}
l.Print()
t.Log(isPalindrome1(l))
}
}
func TestPalindrome2(t *testing.T) {
strs := []string{"heooeh","hello","heooeh","a",""}
for _,str1 := range strs {
l := NewLinkedList()
for _,c := range str1 {
l.InsertToTail(string(c))
}
l.Print()
t.Log(isPalindrome2(l))
l.Print()
}
}
链表实现：
package main
import "fmt"
type ListNode struct{
next *ListNode
value interface{}
}
type LinkedList struct {
head *ListNode
length uint
}
func NewListNode(v interface{}) *ListNode{
return &ListNode{nil,v}
}
func NewLinkedList() *LinkedList {
return &LinkedList{NewListNode(0),0}
}
func (this *ListNode) GetNext() *ListNode {
return this.next
}
func (this *ListNode) GetValue() interface{} {
return this.value
}
func (this *LinkedList) InsertToAfter(p *ListNode,v interface{}) bool {
if nil == p {
return false
}
newNode := NewListNode(v)
oldNext := p.next
p.next = newNode
newNode.next = oldNext
this.length ++
return true
}
func (this *LinkedList) InsertToHead(v interface{}) bool {
return this.InsertToAfter(this.head,v)
}
func (this *LinkedList) InsertToTail(v interface{}) bool {
cur := this.head
for nil != cur.next {
cur = cur.next
}
return this.InsertToAfter(cur,v)
}
func (this *LinkedList) FindByIndex(index uint) *ListNode {
if index > this.length {
return nil
}
cur := this.head.next
var i uint = 0
for ; i < index; i++ {
cur = cur.next
}
return cur
}
func (this *LinkedList) DeleteNode(p *ListNode) bool {
if nil == p {
return false
}
cur := this.head.next
pre := this.head
for nil != cur {
if cur == p {
break
}
pre = cur
cur = cur.next
}
if nil == cur {
return false
}
pre.next = p.next
p = nil
this.length --
return true
}
func (this *LinkedList) Print() {
cur := this.head.next
format := ""
for cur != nil {
format += fmt.Sprintf("+%v",cur.GetValue())
cur = cur.next
if nil != cur {
format += "->"
}
}
fmt.Println(format)
}
//test
package main
import "testing"
func TestInsertToHead(t *testing.T) {
l := NewLinkedList()
for i := 0; i < 10; i++ {
l.InsertToHead(i+1)
}
l.Print()
}
func TestInsertToTail(t *testing.T) {
l := NewLinkedList()
for i := 0; i < 10; i++ {
l.InsertToTail(i+1)
}
l.Print()
}
func TestFindByIndex(t *testing.T) {
l := NewLinkedList()
for i := 0; i < 10; i++ {
l.InsertToTail(i+1)
}
t.Log(l.FindByIndex(0))
t.Log(l.FindByIndex(9))
t.Log(l.FindByIndex(10))
}
func TestDeleteNode(t *testing.T) {
l := NewLinkedList()
for i := 0; i < 10; i++ {
l.InsertToTail(i+1)
}
l.Print()
t.Log(l.DeleteNode(l.head.next.next))
l.Print()
}
