链表（四）

作者: 小董不太懂 | 来源:发表于2019-10-19 22:11 被阅读0次

链表（四）
234. Palindrome Linked List
week 2019-07-14
腾讯优图常见算法题
链表(四)——判断链表入环点
数据结构（四）静态链表、循环链表、双向链表
链表基础
双向链表&双向循环链表
C语言(四-链表)
4.链表（四）

荒废了一段时间，这段时间实验室事情多，就没怎么看数据结构（悲痛）。

什么是单向循环链表？

顾名思义，单向循环链表，就是在单向链表的基础上做一些改动，实现链表循环，即将原本尾节点的next指向None，现指向链表的头节点，这样一来就实现了所谓的单项循环链表。

单向循环链表

了解了大致的概念之后，我们需要用代码实现这个单向循环链表，单向循环链表的代码也是在单向链表的代码基础上进行更改。
节点的构造是没有区别的，可以直接用单向链表的代码。
那关于首节点，我们是不是需要一些改动啊，比如让它指向自己。

class Node():
    '''节点'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    '''单向循环链表'''
    def __init__(self,node=None):
        #内部私有函数，链表头的初始化，可以直接建立空链表
        self.__head = node
        if node:
            node.next = node#self.__head指向node，如果node存在那还需要建立一个回环，让  note.next指向自己本身

那么关于探空的功能呢?是不是也无需更改？答案是无需更改

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head == None

实现求长度的功能：

单向链表结束的条件：cur == None或者cur == self.__head
能否用在我们的单项循环链表呢，答案是不可以，因为单向链表的判断语句不仅在尾结点上复合，且在头节点也符合，故不可用。
单向循环链表的结束条件：cur.next == seif.__head
但是我们的count初始值为1，如果按照这个初值走，最后会少算一个节点，故初始值改为1。

    def length(self):
        """返回链表的长度"""
        #cur游标，用来移动遍历节点
        #count，用来记录节点数量
        count = 1
        cur = self.__head
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

考虑一下，若链表为空链表怎么处理呢，若链表只有一个节点呢？

  def length(self):
        """返回链表的长度"""
        #cur游标，用来移动遍历节点
        #count，用来记录节点数量
        count = 1
        if self.is_empty():
            return 0
        cur = self.__head
        while cur.next != self.__head:#满足仅有一个节点的选项
            count += 1
            cur = cur.next
        return count

如何实现遍历功能：
如果我们使用单向链表的原代码，会发现忽略了打印尾结点，所以最后要加一个打印。
考虑特殊情况，若这个单向循环链表为空链表呢？我们可以预先做个判断，若为空则直接返回，不进行任何操作。
若只含有一个节点呢？直接看代码吧。

    def travel(self):
        """遍历链表"""
        cur = self.__head
        if self.is_empty():
            return 
        while cur != self.__head:
            print(cur.elem,end=' ')
            cur = cur.next
        print(cur.next,end=' ')

通过代码分析，若只含有一个节点，程序不会执行while循环，而是直接打印这个节点。

实现头插法（add）:

方法一这个主要是自己要理解
方法二
这个方法比较容易理解，首先就是移动游标找到尾结点，当终止while循环的时候，游标cur所指向的位置恰好是尾结点，然后将添加的新节点node的node.next指向原首节点也就是self.__head，然后让self.__head指向node，最后将尾结点的next，指向我们新添加的这个头节点，即cur.next指向node或者也可以指向self.__head，因为此时self.head就指向node。
考虑一下特殊情况，当链表为空链表时，那么self.__head指向的便是None，cur就在None的位置了，但是None怎么可能会有next呢？显然程序无法满足空链表的头插需求；现在考虑一下只有一个节点的链表是否符合要求呢？显然符合要求；下面是代码实现。

  def add(self, item):
        """头部添加节点"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            node.next = self.__head
            self.__head = node
            cur.next = node

实现尾插法：

方法一这个应该不难理解
方法二这个也不难理解

那我们直接上代码吧：

    def append(self, item):
        """尾部添加节点"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.next = self.__head

验证一下，若单向循环链表只有一个节点怎么办?是不是程序依旧可以实现啊。

实现随机插入的（insert）方法：

我们直接先码一下，单向链表的代码，看看怎么更改
因为随机插入涉及的头插和尾插都是调用，所以我们这里就不在更改，因为已经可以实现；唯一需要更改的就是else语句，也就是涉及到中间插入的问题，但是单向循环链表的中间插入和单向链表的中间插入并没有什么区别啊，所以更无需更改。所以整体同单向链表一致，无需再做任何更改。
实现查找某个元素的功能：单向链表
我们直接从这个单向链表中更改：
while语句的条件存在问题，要改成while cur.next ！= self.head
这样一来if条件判断到最后一个元素的时候，就会终止循环了，而不再进行判断，其次还需要考虑的问题是特殊情况，比如空链表或者仅有一个节点的情况(直接上代码，按照代码进行分析)。

    def search(self, item):
        """查找节点是否存在"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        if cur.elem == item:
            return True
        return False

我们考虑一下，单个节点，代码也完全可以实现预期目标。

实现删除节点的功能：观察代码，不能拿发现这个删除首节点的情况是最复杂的，因为涉及要遍历到尾节点，然后改变尾节点的指向。如果是删除中间节点的话，首尾节点无需更改，直接更改中间节点的指向即可。但同时当cur指向尾节点的时候，会忽略尾节点的判断，所以最后要重新判断一下尾节点的问题。接下来就是考虑首届点删除的问题了。还要考虑特殊情况：

判断是否为空链表，若为空直接返回。
如果仅有一个节点，那么程序直接跳出while循环，执行pre.next但pre指向的是None没有next ,需要让head直接指向None。
总程序如下：

   def remove(self, item):
        """删除一个节点"""
        if self.is_empty():
            return
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                #先判断是否为头节点，然后再去处理头节点
                if cur == self.__head:#头节点的情况下
                    rear = self.__head
                    self.__head = cur.next
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:#在中间删除
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
        if cur.elem == item:#退出循环cur指向尾节点，在尾部删除
            if cur == self.__head:#链表只有一个节点
                self.__head = None
        else:
            pre.next = cur.next

总体代码：

class Node():
   '''节点'''
   def __init__(self,elem):
       self.elem = elem
       self.next = None

class SingleCycleLinkList(object):
   '''单向循环链表'''
   def __init__(self,node=None):
       #内部私有函数，链表头的初始化，可以直接建立空链表
       self.__head = node
       if node:
           node.next = node#self.__head指向node，如果node存在那还需要建立一个回环，让  note.next指向自己本身

   def is_empty(self):
       """判断链表是否为空"""
       return self.__head == None

   def length(self):
       """返回链表的长度"""
       #cur游标，用来移动遍历节点
       #count，用来记录节点数量
       count = 1
       if self.is_empty():
           return 0
       cur = self.__head
       while cur.next != self.__head:#满足仅有一个节点的选项
           count += 1
           cur = cur.next
       return count

   def travel(self):
       """遍历链表"""
       cur = self.__head
       if self.is_empty():
           return
       while cur != self.__head:
           print(cur.elem,end=' ')
           cur = cur.next
       print(cur.next,end=' ')

   def add(self, item):
       """头部添加节点"""
       node = Node(item)
       if self.is_empty():
           self.__head = node
           node.next = node
       else:
           cur = self.__head
           while cur.next != self.__head:
               cur = cur.next
           node.next = self.__head
           self.__head = node
           cur.next = node

   def append(self, item):
       """尾部添加节点"""
       node = Node(item)
       if self.is_empty():
           self.__head = node
           node.next = self.__head
       else:
           cur = self.__head
           while cur.next != self.__head:
               cur = cur.next
           cur.next = node
           node.next = self.__head

   def insert(self, pos, item):
       """在指定位置添加节点"""
       pre = self.__head
       count = 0
       if pos <= 0:
           self.add(item)
       elif pos >= (self.length()-1):
           self.append(item)
       else:
           while count < (pos-1):
               count += 1
               pre = pre.next
           node = Node(item)
           node.next = pre.next
           pre.next = node

   def remove(self, item):
       """删除一个节点"""
       if self.is_empty():
           return
       cur = self.__head
       pre = None
       while cur.next != self.__head:
           if cur.elem == item:
               #先判断是否为头节点，然后再去处理头节点
               if cur == self.__head:#头节点的情况下
                   rear = self.__head
                   self.__head = cur.next
                   while rear.next != self.__head:
                       rear = rear.next
                   self.__head = cur.next
                   rear.next = self.__head
               else:#在中间删除
                   pre.next = cur.next
               break
           else:
               pre = cur
               cur = cur.next
       if cur.elem == item:#退出循环cur指向尾节点，在尾部删除
           if cur == self.__head:#链表只有一个节点
               self.__head = None
       else:
           pre.next = cur.next


   def search(self, item):
       """查找节点是否存在"""
       if self.is_empty():
           return False
       cur = self.__head
       while cur.next != self.__head:
           if cur.elem == item:
               return True
           else:
               cur = cur.next
       if cur.elem == item:
           return True
       return False



if __name__ == '__main__':
   li = SingleCycleLinkList()
   print(li.is_empty())
   print(li.length())

   li.append(1)
   li.append(2)
   print(li.is_empty())
   print(li.length())

   li.append(3)
   li.append(4)
   li.add(10)
   li.add(20)
   li.insert(2,30)
   li.insert(10,1000)
   li.insert(0,999)
   li.travel()
   print()
   print(li.search(20))
   print(li.search(123))
   li.travel()
   li.remove(999)
   li.travel()
   li.remove(1000)
   li.travel()
   li.remove(30)
   li.travel()

测试结果：

D:\anaconda\python.exe D:/bilibili大学/简书代码/singe_cycle_link_list.py
True
0
False
2
<__main__.Node object at 0x000001C2CEDBB390> 
True
False
<__main__.Node object at 0x000001C2CEDBB390> <__main__.Node object at 0x000001C2CEDBB438> <__main__.Node object at 0x000001C2CEDBB438> <__main__.Node object at 0x000001C2CEDBB438> 
Process finished with exit code 0

链表（四）
荒废了一段时间，这段时间实验室事情多，就没怎么看数据结构（悲痛）。什么是单向循环链表？了解了大致的概念之后，我...
234. Palindrome Linked List
知识点：快慢指针链表反转链表反转的四行代码必须熟记
week 2019-07-14
四数之和括号生成合并K个链表
腾讯优图常见算法题
最常见的：一、两数之和二、链表反转三、环状链表四、快排五、合并两个有序链表六、最大子序和七、最长上...
链表(四)——判断链表入环点
LeetCode_142_LinkedListCycleII 题目分析：解法：
数据结构（四）静态链表、循环链表、双向链表
静态链表：数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（...
链表基础
链表基础链表长度链表为空链表结构链表增加
双向链表&双向循环链表
链表分为：单链表、单向循环链表、双向链表、双向循环链表本节主要说明：双向链表、双向循环链表定义结点一、双向链表...
C语言(四-链表)
链表因为数组必须事先确定大小，不能实现动态申请、释放。而使用malloc动态内存分配也无法实现，malloc申请...
4.链表（四）
题目汇总https://leetcode-cn.com/tag/linked-list/725. 分隔链表中等（有...