数据结构与算法 --- 3(单向循环链表)(Swift)

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

1585876252560.jpg

//单向循环链表
class CycleLinkList {
    
    var linkList:Node?

    /*
    4.1 循环链表创建!
    2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
    
    1. 判断是否第一次创建链表
       YES->创建一个新结点,并使得新结点的next 指向自身;
       NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next指向首元结点;
    */
    func createList(intArr:[Int]) {
        
        for value in intArr {
            if linkList == nil {
                //此时链表是空，创建一个新的结点，并next指向自己
                linkList = Node()
                linkList?.data = value
                linkList?.next = linkList
            }else {
                //此时链表不是空的，寻找链表的尾结点，使尾结点的next=新结点，新节点的next指向头结点
                var target = linkList
                while target?.next != linkList {
                    target = target?.next
                }
                
                let temp = Node()
                temp.data = value
                temp.next = linkList
                target?.next = temp
                
            }
        }
    }
    
    
    //遍历循环链表
    func show() {
        
        var temp:Node?
        temp = linkList
        
        repeat {
            print("value :: \(temp?.data ?? -1)")
            temp = temp?.next
        }while(temp != linkList)
    }
    
    //插入
    func insert(index:Int, value:Int) {
        
        if linkList == nil {
            return
        }
        
        var temp:Node, target:Node
        if index == 0 {
            //如果插入的位置为0,则属于插入首元结点,所以需要特殊处理
            //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
            //2. 找到链表最后的结点_尾结点,
            //3. 让新结点的next 执行头结点.
            //4. 尾结点的next 指向新的头结点;
            //5. 让头指针指向temp(临时的新结点)
            
            temp = Node()
            temp.data = value
            
            target = linkList!
            while target.next != linkList {
                target = target.next!
            }
            
            temp.next = linkList
            target.next = temp
            linkList = temp
            
            
        }else {
            //如果插入的位置在其他位置;
            //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
            //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
            //3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
            //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;

            temp = Node()
            temp.data = value
            
            target = linkList!
            var i:Int = 0
            while target.next != linkList && i < index-1 {
                target = target.next!
                i += 1
            }
            
            temp.next = target.next
            target.next = temp
            
        }
    }
    
    //删除
    func delete(index:Int) {
        if linkList == nil { return }
        var temp = linkList
        var target:Node?
        
        if index == 0 {
            //1.如果删除到只剩下首元结点了,则直接将LinkList置空
            if linkList!.next === linkList! {
                linkList = nil
                return
            }
            
            //2.链表还有很多数据,但是删除的是首结点;
            //1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点
            //2. 新结点做为头结点,则释放原来的头结点
            target = linkList!
            while target?.next != linkList {
                target = target?.next!
            }
            
            linkList = linkList?.next
            target?.next = linkList
            
        }else {
            //如果删除其他结点--其他结点
            //1. 找到删除结点前一个结点target
            //2. 使得target->next 指向下一个结点
            
            target = linkList!
            var i:Int = 0
            while target?.next != linkList && i < index-1 {
                target = target?.next
                i += 1
            }
            temp = target?.next
            target?.next = temp?.next
        }
    }
}

let link = CycleLinkList()
link.createList(intArr: [1,5,16,4,8])
link.show()
print(" Will Insert -------- ")
link.insert(index: 1, value: 2)
link.show()
print(" Will Delete -------- ")
link.delete(index: 0)
link.delete(index: 3)
link.show()

输出的结果

1585842394631.jpg