链表实现-回文palindrome判断

1.数字回文判断(逆转，分离未位，砍掉个位,保存原来)

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()
}

巴特西

链表实现-回文palindrome判断

最新文章

热门文章