Python 力扣刷题之单链表专场!例题20+ 属性和方法60+(2)

简介: Python 力扣刷题之单链表专场!例题20+ 属性和方法60+

10. 链表分组


Partition List (#86)

给定一个链表和一个整数,把链表分成“小于指定数”和“不小于指定数”的二组连接在一起,并且各组元素在本组中的先后位置保持与原链表相同。


示例

输入: 1->4->3->2->5->2->None, x = 3

输出: 1->2->2->4->3->5->None

    def partition(self,x):
        if not self.head.next: return self
        gt,lt = Node(),Node()
        ptr1,ptr2,ptr = gt,lt,self.head
        while ptr:
            if ptr.val<x:
                ptr1.next = Node(ptr.val)
                ptr1 = ptr1.next
            else:
                ptr2.next = Node(ptr.val)
                ptr2 = ptr2.next
            ptr = ptr.next
        ptr1.next = lt.next
        return List(gt.next)


>>> list1 = List(1,4,3,2,5,2); x = 3
>>> list1.partition(x)
[1->2->2->4->3->5->None]
>>> 




11. 反转链表中一段节点

Reverse Linked List (a part of NodeList)  (#92)

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.



示例

输入: 1->2->3->4->5->None, m = 2, n = 4

输出: 1->4->3->2->5->None



12. 重排链表


Reorder List (#143)

Given a singly linked list L: L0→L1→…→Ln-1→Ln,  

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

给定一个链表,不允许修改数据域,按“从头尾向中间的顺序“重排节点。


示例

   Given 1->2->3->4, reorder it to 1->4->2->3.

   Given 1->2->3->4->5, reorder it to 1->5->2->4->3.



方法一:先遍历出长度和倒序链表,然后把两个链表的前半部分混插。

    def reorder(self):
        if not self.head.next: return self
        size,tmp,ptr = 0,Node(),self.head
        while ptr:
            size += 1
            tmp = Node(ptr.val,tmp)
            ptr = ptr.next
        ret = Node()
        ptr1,ptr2,ptr = self.head,tmp,ret
        for _ in range(size//2):
            ptr.next = Node(ptr1.val)
            ptr,ptr1 = ptr.next,ptr1.next
            ptr.next = Node(ptr2.val)
            ptr,ptr2 = ptr.next,ptr2.next
        if size%2: ptr.next = Node(ptr1.val)
        return List(ret.next)


 >>> a = List(*range(1,5))
>>> a.reorder()
[1->4->2->3->None]
>>> b = List(*range(1,6))
>>> b.reorder()
[1->5->2->4->3->None]
>>> c = List(*range(1,7))
>>> c.reorder()
[1->6->2->5->3->4->None]
>>> 


方法二:使用基本方法中的pophead(),poptail()反复弹出头尾节点,用弹出值新建一个链表。

    def reorderHT(self):
        if not self.head.next or not self.head.next.next:
            return self
        ret,self = Node(),List(self)
        ptr = ret
        while self:
            ptr.next = Node(self.pophead())
            ptr = ptr.next
            try: ptr.next = Node(self.poptail())
            except: break
            ptr = ptr.next
        return List(ret.next)
>>> a = List(1,2,3,4)
>>> a.reorderHT()
[1->4->2->3->None]
>>> b = List(1,2,3,4,5)
>>> b.reorderHT()
[1->5->2->4->3->None]
>>> c = List(1,2,3,4,5,6)
>>> c.reorderHT()
[1->6->2->5->3->4->None]
>>> c
[1->2->3->4->5->6->None]
>>> 




13. 链表插入排序

Insertion Sort List (#147)

Sort a linked list using insertion sort.


示例

输入: 4->2->1->3

输出: 1->2->3->4

输入: -1->5->3->4->0

输出: -1->0->3->4->5

已定义的基本方法中sorted(),sort()已能实现排序功能,但是排序时直接比较数据域的。

>>> list1 = List(6,3,4,5,2,1)
>>> list1.sorted()
[1->2->3->4->5->6->None]
>>> list1
[6->3->4->5->2->1->None]
>>> list1.sort()
[1->2->3->4->5->6->None]
>>> list1
[1->2->3->4->5->6->None]
>>> 



插入排序:

    def insertionSort(self):
        if not self.head.next: return self
        ret = Node()
        ptr,ptr1 = List(self).head,ret
        while ptr:
            Next = ptr.next
            while ptr1.next and ptr1.next.val<ptr.val:
                ptr1 = ptr1.next
            ptr.next,ptr1.next = ptr1.next,ptr
            ptr,ptr1 = Next,ret
        return List(ret.next)
>>> list1 = List(4,2,1,3)
>>> list1.insertionSort()
[1->2->3->4->None]
>>> list1
[4->2->1->3->None]
>>> list2 = List(-1,5,3,4,0)
>>> list2.insertionSort()
[-1->0->3->4->5->None]
>>> list2
[-1->5->3->4->0->None]
>>> 



14. 链表归并排序


Sort List (#148)

Sort a linked list in O(n log n) time using constant space complexity.

归并排序: 时间复杂度 O(n log n),空间复杂度 O(1)



15. 删除指定值的所有节点


Remove Linked List Elements (#203)

删除给定链表中所有数值域等于指定值val的节点。

示例

输入: 1->2->6->3->4->5->6, val = 6

输出: 1->2->3->4->5

    def removeValues(self,val):
        if not self.head: return self
        ret = Node()
        ptr1,ptr2 = ret,self.head
        while ptr2:
            if ptr2.val!=val:
                ptr1.next = Node(ptr2.val)
                ptr1 = ptr1.next
            ptr2 = ptr2.next
        return List(ret.next)
>>> list1 = List(1,2,6,3,4,5,6); val = 6
>>> list1.removeValues(val)
[1->2->3->4->5->None]
>>> list1.removeValues(0)
[1->2->6->3->4->5->6->None]
>>> 

方法二:迭代法

    def removeElements(self,val):
        if isinstance(self,List):
            self = List(self.head.next) if self.head.val==val else List(self.head)
            self = self.head
        while self and self.val==val: self = self.next
        if self: self.next = List.removeElements(self.next,val)
        return self


>>> list1 = List(1,2,6,3,4,5,6); val = 6
>>> list1.removeElements(val)
1->2->3->4->5->None
>>> list1
[1->2->6->3->4->5->6->None]
>>> list2 = List(3,1,2,3,3,4,3,5,5,3); val = 3
>>> list2.removeElements(val)
1->2->4->5->5->None
>>> list2
[3->1->2->3->3->4->3->5->5->3->None]
>>> 



16. 反转链表


Reverse Linked List (#206)

Reverse a singly linked list.


链表的全部反转,这是很基础的方法。上面的第6题、第11题中已有部分的反转。

已定义的基本方法中已有 __reversed__、.reverse() 可以完成反转,把它们的代码稍作改进,相当于直接改变链表的指针方向,而不是用Node()嵌套新建一个链表,本质是一样的。

    def reverseList(self):
        ret,ptr = None,self.head
        while ptr: ptr.next,ret,ptr = ret,ptr,ptr.next
        self.head = ret
        return self


>>> a = List(range(1,6))
>>> a.reverseList()
[5->4->3->2->1->None]
>>> b = List(range(0,10,2))
>>> b.reverseList()
[8->6->4->2->0->None]
>>> c = List(1)
>>> c.reverseList()
[1->None]
>>> d = List()
>>> d.reverseList()
[None->None]
>>> b = List(range(0,9,2))
>>> b.reverseList()
[8->6->4->2->0->None]
>>> b = List(range(0,3,2))
>>> b.reverseList()
[2->0->None]
>>> 




17.  回文链表


Palindrome Linked List (#234)

判断给定链表是否为回文链表,即链表与反转后的一致。


示例

    Input: 1->2
    Output: False
    Input: 1->2->2->1
    Output: True
    def isPalindrome(self):
        if not self.head.next:
            return True
        ptr,tmp = self.head,[]
        while ptr:
            tmp.append(ptr.val)
            ptr = ptr.next
        ptr = self.head
        while ptr:
            if ptr.val!=tmp.pop():
                return False
            ptr = ptr.next
        return True
>>> list1 = List(1,2)
>>> list1.isPalindrome()
False
>>> list2 = List(1,2,2,1)
>>> list2.isPalindrome()
True
>>> list3 = List(1,2,3,2,1)
>>> List.isPalindrome(list3)
True
>>> 


直接调用已定义的基本方法__reversed__、__eq__、__contains__也能办到:

>>> list1 = List(1,2)
>>> list1 in reversed(list1)
False
>>> list1 == reversed(list1)
False
>>> list2 = List(1,2,2,1)
>>> list2 in reversed(list2)
True
>>> list2 == reversed(list2)
True
>>> 



18. 删除指定节点

Delete Node in a Linked List (#237)

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Given linked list -- head = [4,5,1,9], which looks like following:
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list
should become 4 -> 1 -> 9 after calling your function.
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should
become 4 -> 5 -> 9 after calling your function.
Note:
The linked list will have at least two elements.
All of the nodes' values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Do not return anything from your function.


与15题类同但只删除一个,如果不像Note中说明的一样:节点的值都是唯一的;那么还延用15题的方法则需要设置一个标记:重复的只不复制第一个。

    def removeVal1(self,val):
        if not self.head: return self
        ret,flag = Node(),True
        ptr1,ptr2 = ret,self.head
        while ptr2:
            if flag and ptr2.val==val:
                flag = False
            else:
                ptr1.next = Node(ptr2.val)
                ptr1 = ptr1.next          
            ptr2 = ptr2.next
        return List(ret.next)
>>> list1 = List(4,5,1,9); val = 5
>>> list1.removeVal1(val)
[4->1->9->None]
>>> list1.removeVal1(1)
[4->5->9->None]
>>> list2 = List(1,2,6,3,4,5,6); val = 6
>>> list2.removeVal1(val)
[1->2->3->4->5->6->None]
>>> 



方法二:遇到指定值,直接跳指下一个节点,self的值会被变更。

    def removeVal2(self,val):
        if not self.head: return self
        if self.head.val==val:
            self.head = self.head.next
        else:
            ptr = self.head
            while ptr.next:
                if ptr.next.val==val:
                    ptr.next = ptr.next.next
                    break
                ptr = ptr.next
        self.head = self.head or Node()
        return self


>>> list1 = List(4,5,1,9); val = 5
>>> list1.removeVal2(val)
[4->1->9->None]
>>> list1.removeVal2(1)
[4->9->None]
>>> list2 = List(1,2,6,3,4,5,6); val = 6
>>> list2.removeVal2(val)
[1->2->3->4->5->6->None]
>>> list2.removeVal2(6)
[1->2->3->4->5->None]
>>> list2.removeVal2(1)
[2->3->4->5->None]
>>> 

直接调用已定义的基本方法.find()和.delete()也可完成:

>>> list1 = List(4,5,1,9); val = 5
>>> list1.delete(list1.find(val))
[4->1->9->None]
>>> list1.delete(list1.find(1))
[4->9->None]
>>> list2 = List(1,2,6,3,4,5,6); val = 6
>>> list2.delete(list2.find(val))
[1->2->3->4->5->6->None]
>>> list2.delete(list2.find(val))
[1->2->3->4->5->None]
>>> list2.delete(list2.find(1))
[2->3->4->5->None]
>>> 




19. 奇偶索引重排


Odd Even Linked List (#328)

给定一个单链表,按节点索引号的奇偶重新排列。


示例

输入: 1->2->3->4->5->NULL

输出: 1->3->5->2->4->NULL

输入: 2->1->3->5->6->4->7->NULL

输出: 2->3->6->7->1->5->4->NULL

    def oddevenIndex(self):
        if not self.head.next: return self
        odd,even,index = Node(),Node(),0
        ptr1,ptr2,ptr = odd,even,self.head
        while ptr:
            index += 1
            if index%2:
                ptr1.next = Node(ptr.val)
                ptr1 = ptr1.next
            else:
                ptr2.next = Node(ptr.val)
                ptr2 = ptr2.next
            ptr = ptr.next
        ptr1.next = even.next
        return List(odd.next)
>>> a = List(*range(1,6))
>>> a.oddevenIndex()
[1->3->5->2->4->None]
>>> b = List(2,1,3,5,6,4,7)
>>> b.oddevenIndex()
[2->3->6->7->1->5->4->None]
>>> 


类似题目:给定一个单链表,按节点数值域的奇偶重新排列。这类按要求分组的都与第10题属于同一类型。

    def oddevenNumber(self):
        if not self.head.next: return self
        odd,even = Node(),Node()
        ptr1,ptr2,ptr = odd,even,self.head
        while ptr:
            if ptr.val%2:
                ptr1.next = Node(ptr.val)
                ptr1 = ptr1.next
            else:
                ptr2.next = Node(ptr.val)
                ptr2 = ptr2.next
            ptr = ptr.next
        ptr1.next = even.next
        return List(odd.next)



>>> a = List(*range(1,6))
>>> a.oddevenNumber()
[1->3->5->2->4->None]
>>> b = List(2,1,3,5,6,4,7)
>>> b.oddevenNumber()
[1->3->5->7->2->6->4->None]
>>> 




20. 两数之和 II


Add Two Numbers II (#445)


You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.


You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:


What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

第一题的变形,本题的链表是正序表示两个整数的非空链表,不允许反转完成加法。


示例


   输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

   输出: 7 -> 8 -> 0 -> 7


    def Add2NumII(self,node):
        len1,len2 = self.size(),node.size()
        ret1,ret2,self = [],[],List(self.head)
        if len1>len2:
            ptr1,ptr2 = self.head,node.head
        else:
            ptr1,ptr2 = node.head,self.head
            len1,len2 = len2,len1
        for _ in range(len1-len2):
            ret1.append(ptr1.val)
            ret2.append(0)
            ptr1 = ptr1.next
        while ptr2:
            ret1.append(ptr1.val)
            ret2.append(ptr2.val)
            ptr1,ptr2 = ptr1.next,ptr2.next
        ret,carry = Node(),0
        for _ in range(len1):
            Sum = carry + ret1.pop() + ret2.pop()
            carry,Sum = divmod(Sum,10)
            ret = Node(Sum,ret)
        if carry: ret = Node(1,ret)
        return ret


>>> list1 = List(7,2,4,3); list2 = List(5,6,4)
>>> list1.Add2NumII(list2)
7->8->0->7->None
>>> list2.Add2NumII(list1)
7->8->0->7->None
>>> list1 = List(5,2,0,8); list2 = List(9,5,5,3,3)
>>> list1.Add2NumII(list2)
1->0->0->7->4->1->None
>>> list2.Add2NumII(list1)
1->0->0->7->4->1->None
>>> 




21 . 链表类设计


Design Linked List (#707)

Design your implementation of the linked list. You can choose to use the singly linked list or the

doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the

value of the current node, and next is a pointer/reference to the next node. If you want to use the

doubly linked list, you will need one more attribute prev to indicate the previous node in the

linked list. Assume all nodes in the linked list are 0-indexed.

Implement these functions in your linked list class:

get(index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.

addAtHead(val) : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

addAtTail(val) : Append a node of value val to the last element of the linked list.

addAtIndex(index, val) : Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.

deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.


Example:
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
linkedList.get(1); // returns 2
linkedList.deleteAtIndex(1); // now the linked list is 1->3
linkedList.get(1); // returns 3


Example:

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
linkedList.get(1); // returns 2
linkedList.deleteAtIndex(1); // now the linked list is 1->3
linkedList.get(1); // returns 3


Note:

All values will be in the range of [1, 1000].

The number of operations will be in the range of [1, 1000].

Please do not use the built-in LinkedList library.

类似的功能在已定义的基本方法中都有:


>>> linkedList = List(1)
>>> linkedList.append(3)
[1->3->None]
>>> linkedList.insert(1,2)
[1->2->3->None]
>>> linkedList[1]
2
>>> linkedList.delete(1)
[1->3->None]
>>> linkedList[1]
3



22 . 链表中间节点


Middle of the Linked List (#876)

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

给定一个非空链表,返回中间节点。如有2个中间节点(节点数为偶数时)返回第2个。


方法一:先遍历出长度,再遍历一半长度

    def middleNode(self):
        if not self.head.next:
            return self.head.val
        ptr,size = self.head,0
        while ptr:
            size += 1
            ptr = ptr.next
        ptr = self.head
        for _ in range(size//2):
            ptr = ptr.next
        return ptr.val
>>> list1 = List(range(1,6))
>>> list1
[1->2->3->4->5->None]
>>> list1.middleNode()
3
>>> list2 = List(range(1,7))
>>> list2
[1->2->3->4->5->6->None]
>>> list2.middleNode()
4
>>>  

方法二:快指针步进2,慢指针步进1,当快指针移到尾部时,慢指针就在中间节点上。

    def middleNodefs(self):
        if not self.head.next: return self.head.val
        fast,slow = self.head,self.head
        while fast:
            if fast.next is None: return slow.val
            fast,slow = fast.next,slow.next
            fast = fast.next
        return slow.val



>>> list1 = List(range(1,6))
>>> list1.middleNodefs()
3
>>> list1 = List(range(1,7))
>>> list1.middleNodefs()
4
>>> 




23 . 下一个大节点


Next Greater Node In Linked List (#1019)


We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.


找出链表中第一个比自己大的节点,没找到则为0。



示例

   输入: [2,1,5]

   输出: [5,5,0]

   输入: [2,7,4,3,5]

   输出: [7,0,5,5,0]

   输入: [1,7,5,1,9,2,5,1]

   输出: [7,9,9,9,0,5,0,0]

    def nextGreaterNode(self):
        ret,ptr = [],self.head
        while ptr:
            cur,tmp = ptr,ptr.val
            while cur:
                if cur.val>tmp:
                    ret.append(cur.val)
                    break
                cur = cur.next
            else:
                ret.append(0)
            ptr = ptr.next
        return ret


>>> a = List([2,1,5])
>>> a.nextGreaterNode()
[5, 5, 0]
>>> b = List([2,7,4,3,5])
>>> b.nextGreaterNode()
[7, 0, 5, 5, 0]
>>> c = List([1,7,5,1,9,2,5,1])
>>> c.nextGreaterNode()
[7, 9, 9, 9, 0, 5, 0, 0]
>>> 

20210817204340750.png

目录
打赏
0
0
0
0
74
分享
相关文章
|
4月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
54 1
|
4月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
71 0
Leetcode第21题(合并两个有序链表)
Python 实现反转、合并链表有啥用?
大家好,我是V哥。本文介绍Python实现反转链表和合并链表的应用场景及代码实现。反转链表适用于时间序列数据展示、回文链表判断等;合并链表则用于大规模数据排序、数据库查询结果集合并等。通过迭代和递归方法实现反转链表,以及合并两个或多个有序链表的算法,帮助开发者解决实际问题。关注V哥,了解更多实用编程技巧。 先赞再看后评论,腰缠万贯财进门。
|
1月前
|
探索 Python 中链表的实现:从基础到高级
链表是一种由节点组成的基础数据结构,每个节点包含数据和指向下一个节点的引用。本文通过Python类实现单向链表,详细介绍了创建、插入、删除节点等操作,并提供示例代码帮助理解。链表在处理动态数据时具有高效性,适用于大量数据变动的场景。文章为初学者提供了全面的入门指南,助你掌握链表的核心概念与应用。
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
104 1
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
44 3
|
4月前
|
HashMap之链表转红黑树(树化 )-treefyBin方法源码解读(所有涉及到的方法均有详细解读,欢迎指正)
本文详细解析了Java HashMap中链表转红黑树的机制,包括树化条件(链表长度达8且数组长度≥64)及转换流程,确保高效处理大量数据。
177 1
|
4月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
48 0
LeetCode第二十四题(两两交换链表中的节点)
|
4月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
57 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
4月前
|
Leecode 101刷题笔记之第四章:和你一起你轻松刷题(Python)
这篇博客是关于LeetCode上使用Python语言解决二分查找问题的刷题笔记,涵盖了从基础到进阶难度的多个题目及其解法。
40 0

热门文章

最新文章