Go-实现单向循环链表

小鱼儿 2022-09-09 02:21 182阅读 0赞

代码片段如下：

/*
     *                    .::::.
     *                  .::::::::.
     *                 :::::::::::
     *             ..:::::::::::'
     *           '::::::::::::'
     *             .::::::::::
     *        '::::::::::::::..
     *             ..::::::::::::.		Utils:单向循环链表
     *           ``::::::::::::::::		Author:崔金朋
     *            ::::``:::::::::'        .:::.
     *           ::::'   ':::::'       .::::::::.
     *         .::::'      ::::     .:::::::'::::.
     *        .:::'       :::::  .:::::::::' ':::::.
     *       .::'        :::::.:::::::::'      ':::::.
     *      .::'         ::::::::::::::'         ``::::.
     *  ...:::           ::::::::::::'              ``::.
     * ```` ':.          ':::::::::'                  ::::..
     *  		           '.:::::'          			':'````..
     */
    
    package main
    
    import "fmt"
    
    // 创建单向循环链表结构
    type CircleLinkedList struct {
    	Id    int
    	Value interface{}
    	Next  *CircleLinkedList
    }
    
    // 创建链表
    func CreateCircleLinkedListNode() *CircleLinkedList {
    	return &CircleLinkedList{}
    }
    
    // 追加节点
    func (c *CircleLinkedList) AppendCircleLinkedListNode(val interface{}) {
    	if val == nil {
    		return
    	}
    
    	if c.Id == 0 {
    		c.Id = 1
    		c.Value = val
    		c.Next = c
    		return
    	}
    
    	listLength := c.GetCircleLinkedListLength()
    	currNode := c.Next
    	for {
    		if currNode.Next == c {
    			currNode.Next = &CircleLinkedList{listLength + 1, val, c}
    			break
    		}
    
    		currNode = currNode.Next
    	}
    }
    
    // 指定位置插入节点
    func (c *CircleLinkedList) InsertCircleLinkedListNode(i int, val interface{}) *CircleLinkedList {
    	listLength := c.GetCircleLinkedListLength()
    	if i < 1 || val == nil || listLength < i {
    		return c
    	}
    
    	var key int
    	currNode := c
    	for {
    		key++
    		if key == i-1 {
    			currNode.Next = &CircleLinkedList{listLength + 1, val, currNode.Next}
    			break
    		}
    
    		if currNode.Next.Id == c.Id {
    			if i == 1 {
    				currNode.Next = &CircleLinkedList{listLength + 1, val, currNode.Next}
    				currNode = currNode.Next
    			}
    
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	if i == 1 {
    		return currNode
    	}
    
    	return c
    }
    
    // 查询节点位置
    func (c *CircleLinkedList) SearchCircleLinkedListNode(i int) *CircleLinkedList {
    	if i < 1 {
    		return nil
    	}
    
    	var key int
    	currNode := c
    	for {
    		key++
    		if key == i-1 {
    			return currNode.Next
    		}
    
    		if currNode.Next == c {
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	return nil
    }
    
    // 指定位置删除节点
    func (c *CircleLinkedList) DeleteCircleLinkedListNode(i int) {
    	listLength := c.GetCircleLinkedListLength()
    	if i <= 0 || i > listLength {
    		return
    	}
    
    	if listLength == 1 {
    		return
    	}
    
    	var key int
    	currNode := c
    	for {
    		key++
    		if key == i-1 {
    			currNode.Next = currNode.Next.Next
    			if i == listLength {
    				currNode = currNode.Next
    			}
    
    			break
    		}
    
    		if currNode.Next == c {
    			if i == 1 {
    				currNode.Next = currNode.Next.Next
    				currNode = currNode.Next
    			}
    
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	c.Id = currNode.Id
    	c.Value = currNode.Value
    	c.Next = currNode.Next
    }
    
    // 打印所有节点
    func (c *CircleLinkedList) PrintlnCircleLinkedListNode() {
    	currNode := c
    	for {
    		fmt.Println("circle list value is: ", currNode.Value)
    		if currNode.Next.Id == c.Id {
    			break
    		}
    
    		currNode = currNode.Next
    	}
    }
    
    // 获取环形链表长度
    func (c *CircleLinkedList) GetCircleLinkedListLength() int {
    	var key int
    	currNode := c
    	for {
    		key++
    		if currNode.Next == c {
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	return key
    }
    
    // 查验是否为回文结构
    func (c *CircleLinkedList) IsPalindromeStructure() bool {
    	listLength := c.GetCircleLinkedListLength()
    	if listLength == 0 {
    		return false
    	}
    
    	if listLength == 1 {
    		return true
    	}
    
    	stack := CommonStack{}
    	currNode := c
    	for {
    		stack.CommonPush(currNode.Value)
    		if currNode.Next.Id == c.Id {
    			break
    		}
    
    		currNode = currNode.Next
    	}
    
    	secondNode := c
    	for {
    		popVal, _ := stack.CommonPop()
    		if popVal != secondNode.Value {
    			return false
    		}
    
    		if secondNode.Next.Id == c.Id {
    			break
    		}
    
    		secondNode = secondNode.Next
    	}
    
    	return true
    }