牛客网---链表（python实现）

迈不过友情╰ 2022-11-05 01:59 256阅读 0赞

### 目录 ###

*   *  一： 判断链表是否有环：
     *  二：合并有序链表：
     *  三：链表中环的入口节点：
     *  四： 反转链表
     *  五：两个链表生成相加链表：
     *  六：两个链表的第一个公共结点：
     *  七： 判断一个链表是否是回文结构：
     *  八： 重排链表：
     *  九：链表中每K个一组翻转：
     *  十：删除链表的倒数第N个结点：
     *  十一：合并K个已排序的链表:
     *  十二： 单链表的选择排序：
     *  十三：链表内指定区间翻转：
     *  十四：删除有序链表中重复的元素：

## 一： 判断链表是否有环： ##

思路： 让快慢指针分别指向头指针，然后快指针每次走两步，慢指针每次走一步，如果两个指针可以相撞，则表示链表有环。

class Solution:
        def hasCycle(self , head ):
            fast = head
            slow = head
            while(fast and fast.next):
                fast = fast.next.next
                slow = slow.next
                if fast == slow:
                    return True
            return False

## 二：合并有序链表： ##

思路： 创建一个新的链表头，然后循环遍历两个链表，分别向新链表中添加元素，当其中一个结束后，让新链表连接还有元素的链表。

class Solution:
        def mergeTwoLists(self , l1 , l2 ):
            # 1: 构造一个新的链表头部
            Head = ListNode(0)
            head = Head
            # 2：循环拼接
            while(l1 and l2):
                if l1.val < l2.val:
                    head.next = l1
                    head = head.next
                    l1 = l1.next
                else:
                    head.next = l2
                    head = head.next
                    l2 = l2.next
            # 3：最后连接剩余的
            if l1:
                head.next = l1
            if l2:
                head.next = l2
            return Head.next # 头的下一个才是真的结点

## 三：链表中环的入口节点： ##

思路：  
特殊情况： 如果根节点是空的，则没有入口节点，直接返回None。  
一般情况：利用快慢指针，如果两个相遇了，则相遇的地方肯定是环中。  
根据计算可知，**头指针移动到入口节点的步数跟相遇点到入口点的距离相等**。因此当两个指针相遇，我们可以使用另外一个指针C从头开始遍历，然后其中一个指针(A或B)继续遍历，当C指针跟A指针再次相碰的时候，就是我们链表中环的入口节点。

class Solution:
        def detectCycle(self , head ):
            if head == None: return None
            fast = head
            slow = head
            while(fast and fast.next):
                fast = fast.next.next
                slow = slow.next
                if fast == slow:
                    while(fast != head):
                        fast = fast.next
                        head = head.next
                    return head
            return None

## 四： 反转链表 ##

思路：  
特殊： 当链表是None，或者链表只有一个我们是不需要反转的。  
一般： next 指针指向下一个， 当前指针的next指向上一个， 前指针向后移动， 当前指针也向后移动。口诀： **next下一个， 我去指向前一个，前移动，我也移动。**

class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            if pHead == None or pHead.next == None: return pHead
            my_pre, my_next = None, None # 前驱指针和后继指针指向None
            phead = pHead
            while(phead):
                my_next = phead.next
                phead.next = my_pre
                my_pre = phead # 这里不能使用 my_pre = my_pre.next 因为开始my_pre 是None
                phead = my_next
            return my_pre # 最后是pre指向头部。

## 五：两个链表生成相加链表： ##

思路：  
特殊： 如果其中一个是空的，则直接返回不为空的链表即可。  
一般： 先将两个链表逆序， 然后用head新增一个表头，然后遍历两个链表，把对应位置数值相加，然后增加新的结点到head中，只不过此时需要逆序添加。添加完成之后，我们还要更新ca（进位）。最后我们要将两个链表向后移动， 但是此时出现一个问题，如果有一个链表下一个结点是空呢？我们要补充结点，值设置为0。最后当两个链表都到头了，则退出循环。此时还有一个问题，就是最后可能还有一个进位，则如果存在，新增一个结点。

class Solution:
        # 逆序链表
        def reverse_list(self, head):
            next, pre = None, None
            while(head):
                next = head.next
                head.next = pre
                pre = head
                head = next
            return pre
        
        def addInList(self , head1 , head2 ):
            # 1：特殊： 如果其中一个是空的，则直接返回另外的一个
            if head1 == None: return head2
            if head2 == None: return head1
            
            # 2: 对链表进行逆序
            head1 = self.reverse_list(head1)
            head2 = self.reverse_list(head2)
            
            # 3: 使用ca表示进位，使用head表示新的表的表头
            head = None
            ca = 0
            
            # 3: 循环生成新的链表：
            while(head1 or head2):
                # 计算对应位的和
                num = head1.val + head2.val + ca
                # 添加新的结点
                next = head
                head = ListNode(num % 10)
                head.next = next
                # 更新ca
                ca = num // 10
                # head1和head2向后移动：
                if head1.next == None and head2.next == None:
                    break
                if head2.next == None: # 给head2增加新的结点
                    add_node = ListNode(0)
                    head2.next = add_node
                if head1.next == None:
                    add_node = ListNode(0)
                    head1.next = add_node
                head1 = head1.next
                head2 = head2.next
            
            # 如果最后还有一个进位则增加一个结点：
            if ca == 1:
                next = head
                head = ListNode(1)
                head.next = next
            return head

## 六：两个链表的第一个公共结点： ##

思路：把一个链表的节点全部加载到一个集合中， 然后遍历另外的一个链表，判断每个节点是否在这个集合中。

class Solution:
        def FindFirstCommonNode(self , pHead1 , pHead2 ):
            if pHead1 == None or pHead2 == None:
                return None
            # 1：创建一个集合，将所有的节点加入到集合中去
            my_set = set()
            while(pHead1):
                my_set.add(pHead1)
                pHead1 = pHead1.next
            # 2：遍历这个链表如果存在则返回该结点
            while(pHead2):
                if pHead2 in my_set:
                    return pHead2
                pHead2 = pHead2.next
            return None

## 七： 判断一个链表是否是回文结构： ##

思路：回文结构： 正序和逆序是相同的。  
1：寻找中间结点：  
2：将后半部分结点进行转置  
3：判断是否是回文链表  
4：将原来的链表恢复。  
5： 返回True/Flase

class Solution:
    
        def isPalindrome(self, head: ListNode) -> bool:
            if head is None:
                return True
    
            # 找到前半部分链表的尾节点并反转后半部分链表
            first_half_end = self.end_of_first_half(head)
            second_half_start = self.reverse_list(first_half_end.next)
    
            # 判断是否回文
            result = True
            first_position = head
            second_position = second_half_start
            while result and second_position is not None:
                if first_position.val != second_position.val:
                    result = False
                first_position = first_position.next
                second_position = second_position.next
    
            # 还原链表并返回结果
            first_half_end.next = self.reverse_list(second_half_start)
            return result    
    
        def end_of_first_half(self, head):
            fast = head
            slow = head
            while fast.next is not None and fast.next.next is not None:
                fast = fast.next.next
                slow = slow.next
            return slow
    
        def reverse_list(self, head):
            previous = None
            current = head
            while current is not None:
                next_node = current.next
                current.next = previous
                previous = current
                current = next_node
            return previous

## 八： 重排链表： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]  
思路：

## 九：链表中每K个一组翻转： ##

## 十：删除链表的倒数第N个结点： ##

## 十一：合并K个已排序的链表: ##

## 十二： 单链表的选择排序： ##

## 十三：链表内指定区间翻转： ##

## 十四：删除有序链表中重复的元素： ##

思路： 双指针。

class Solution:
        def deleteDuplicates(self , head ):
            if not head:
                return head
            pre = head.next
            afr = head
            while pre:
                tmp = pre.next
                if pre.val == afr.val:
                    afr.next = tmp
                    pre = tmp
                else:
                    afr = pre
                    pre = tmp
            return head

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]: /images/20221023/9488d15cc2a443408926c94306e24c81.png