• 链表试题（Python实现）

    目录

    1. 反转链表

    2. 链表内指定区间反转（反转链表 II）

    3. 链表中的节点每k个一组翻转

    4. 链表相加（反转链表）

    5. 链表的中间结点（快慢指针）

    6. 链表中倒数第k个结点（快慢指针）

    7. 删除链表的倒数第n个节点（快慢指针）

    8. 回文链表（判断是否为回文：快慢指针+反转链表）

    9. 合并两个有序链表

    10. 合并k个已排序的链表

    11. 相交链表（两个链表的公共结点）

    12. 判断链表中是否有环（环形链表）

    13. 链表中环的入口结点

    14. 单链表的排序

    15. 链表的奇偶位置重排

    16. 删除有序链表中重复的元素

    17. 删除有序链表中出现重复的元素

    1. class ListNode:
    2.     def __init__(self, val=0, next=None):
    3.         self.val = val
    4.         self.next = next

    1. 反转链表

    206. 反转链表 - 力扣（LeetCode）

    1. class Solution:
    2.     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    3.         res = None
    4.         cur = head
    5.         while cur:
    6.             curNext = cur.next
    7.             cur.next = res
    8.             res = cur
    9.             cur = curNext
    10.         return res

    2. 链表内指定区间反转（反转链表 II）

    链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

    1. class Solution:
    2.     def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
    3.         # [1] 哨兵节点
    4.         dummyNode = ListNode(-1)
    5.         dummyNode.next = head
    6.  
    7.         # [2] pre指向反转区间的前一个节点
    8.         pre = dummyNode
    9.         for _ in range(m-1):
    10.             pre = pre.next
    11.         
    12.         # [3] cur指向反转区间的第一个节点，开始反转
    13.         cur = pre.next
    14.         for _ in range(n-m):
    15.             curNext = cur.next
    16.             cur.next = curNext.next
    17.             curNext.next = pre.next
    18.             pre.next = curNext
    19.         return dummyNode.next

    3. 链表中的节点每k个一组翻转

    链表中的节点每k个一组翻转_牛客题霸_牛客网 (nowcoder.com)

    递归实现

    1. class Solution:
    2.     def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
    3.         # [1] 找到当前要翻转的尾部
    4.         tail = head
    5.         for _ in range(k):
    6.             # 如果走到链表尾则直接返回结果head
    7.             if tail == None:
    8.                 return head
    9.             tail = tail.next
    10.         # [2] 翻转（在到达当前尾节点tail时）
    11.         newHead = None
    12.         cur = head
    13.         while cur != tail:
    14.             curNext = cur.next
    15.             cur.next = newHead
    16.             newHead = cur
    17.             cur = curNext
    18.         # [3] 当前尾指向下一段要翻转的链表
    19.         head.next = self.reverseKGroup(tail, k)
    20.         return newHead

    4. 链表相加（反转链表）

    链表相加(二)_牛客题霸_牛客网 (nowcoder.com)

    1. class Solution:
    2.     # 反转链表
    3.     def reverse(self, head: ListNode) -> ListNode:
    4.         res = None
    5.         cur = head
    6.         while cur:
    7.             curNext = cur.next
    8.             cur.next = res
    9.             res = cur
    10.             cur = curNext
    11.         return res
    12.     def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
    13.         if head1 is None: return head2
    14.         if head2 is None: return head1
    15.         # 反转链表
    16.         head1 = self.reverse(head1)
    17.         head2 = self.reverse(head2)
    18.         # 创建头节点
    19.         head = ListNode(-1)
    20.         cur = head
    21.         # 记录进位数
    22.         count = 0
    23.         while head1 is not None or head2 is not None:
    24.             val = count
    25.             if head1 is not None:
    26.                 val += head1.val
    27.                 head1 = head1.next
    28.             if head2 is not None:
    29.                 val += head2.val
    30.                 head2 = head2.next
    31.             count = val//10
    32.             cur.next = ListNode(val%10)
    33.             cur = cur.next
    34.         # 判断最终是否需要进位
    35.         if count>0:
    36.             cur.next = ListNode(count)
    37.         return self.reverse(head.next)

    5. 链表的中间结点（快慢指针）

    876. 链表的中间结点 - 力扣（LeetCode）

    1. class Solution:
    2.     def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    3.         fast, slow = head, head
    4.         while fast and fast.next:
    5.             fast = fast.next.next
    6.             slow = slow.next
    7.         return slow

    6. 链表中倒数第k个结点（快慢指针）

    链表中倒数最后k个结点_牛客题霸_牛客网 (nowcoder.com)

    1. class Solution:
    2.     def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
    3.         fast, slow = pHead, pHead
    4.         for _ in range(k):
    5.             if not fast:
    6.                 return None
    7.             fast = fast.next
    8.         while fast:
    9.             slow = slow.next
    10.             fast = fast.next
    11.         return slow

    7. 删除链表的倒数第n个节点（快慢指针）

    删除链表的倒数第n个节点_牛客题霸_牛客网 (nowcoder.com)

    1. class Solution:
    2.     def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:
    3.         if head is None: return None
    4.         slow, fast = head, head
    5.         for _ in range(n):
    6.             fast = fast.next
    7.         # 如果n大于链表的长度，则删除链表的第一个节点（返回head.next）
    8.         if fast is None:
    9.             return head.next
    10.         while fast.next:
    11.             slow = slow.next
    12.             fast = fast.next
    13.         slow.next = slow.next.next
    14.         return head

    8. 回文链表（判断是否为回文：快慢指针+反转链表）

    234. 回文链表 - 力扣（LeetCode）

    快慢指针找到中间结点，然后反转链表，最后判断是否一致

    1. class Solution:
    2.     def isPalindrome(self, head: Optional[ListNode]) -> bool:
    3.         if head is None: return True
    4.         fast = slow = head
    5.         # [1] slow 找到中间结点
    6.         while fast.next and fast.next.next:
    7.             fast = fast.next.next
    8.             slow = slow.next
    9.  
    10.         # [2] 反转后半段，以newHead为头结点
    11.         newHead = None
    12.         cur = slow.next
    13.         slow.next = None
    14.         while cur:
    15.             curNext = cur.next
    16.             cur.next = newHead
    17.             newHead = cur
    18.             cur = curNext
    19.  
    20.         # [3] 判断
    21.         while newHead:
    22.             if head.val != newHead.val:
    23.                 return False
    24.             head = head.next
    25.             newHead = newHead.next
    26.         return True

     利用Python特性实现：存入数组直接逆置判断

    1. class Solution:
    2.     def isPalindrome(self, head: Optional[ListNode]) -> bool:
    3.         val = []
    4.         while head:
    5.             val.append(head.val)
    6.             head = head.next
    7.         return val == val[::-1]

    9. 合并两个有序链表

    21. 合并两个有序链表 - 力扣（LeetCode）

    1. class Solution:
    2.     def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    3.         newHead = ListNode(-1)
    4.         cur = newHead
    5.         while list1 and list2:
    6.             if list1.val <= list2.val:
    7.                 cur.next = list1
    8.                 list1 = list1.next
    9.             else:
    10.                 cur.next = list2
    11.                 list2 = list2.next
    12.             cur = cur.next
    13.         if list1:
    14.             cur.next = list1
    15.         else:
    16.             cur.next = list2
    17.         return newHead.next

    10. 合并k个已排序的链表

    合并k个已排序的链表_牛客题霸_牛客网 (nowcoder.com)

    思路1：归并+分治

    1. class Solution:
    2.     # 合并两个有序链表
    3.     def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
    4.         newHead = ListNode(-1)
    5.         cur = newHead
    6.         while list1 and list2:
    7.             if list1.val <= list2.val:
    8.                 cur.next = list1
    9.                 list1 = list1.next
    10.             else:
    11.                 cur.next = list2
    12.                 list2 = list2.next
    13.             cur = cur.next
    14.         if list1:
    15.             cur.next = list1
    16.         else:
    17.             cur.next = list2
    18.         return newHead.next
    19.  
    20.     # 合并k个已排序的链表
    21.     def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    22.         return self.divideMerge(lists, 0, len(lists) - 1)
    23.  
    24.     # 划分合并区间
    25.     def divideMerge(self, lists: List[ListNode], left: int, right: int) -> ListNode:
    26.         if left > right:
    27.             return None
    28.         elif left == right:
    29.             return lists[left]
    30.         # 从中间分成两段，再将合并好的两段合并
    31.         mid = (left + right) // 2
    32.         return self.mergeTwoLists(
    33.             self.divideMerge(lists, left, mid), self.divideMerge(lists, mid + 1, right))

    思路2：优先队列（堆）

    1. from queue import PriorityQueue
    2. class Solution:
    3.     def mergeKLists(self , lists: List[ListNode]) -> ListNode:
    4.         # 小根堆
    5.         pg = PriorityQueue()
    6.         # 遍历所有链表第一个元素，不为空则加入小根堆pg
    7.         for i in range(len(lists)):
    8.             if lists[i] is not None:
    9.                 pg.put((lists[i].val, i))
    10.                 lists[i] = lists[i].next
    11.         # 结果链表
    12.         res = ListNode(-1)
    13.         cur = res
    14.         # 直到小根堆为空
    15.         while not pg.empty():
    16.             # 取出最小元素
    17.             val,idex = pg.get()
    18.             cur.next = ListNode(val)
    19.             cur = cur.next
    20.             # 添加该链表的下一个元素
    21.             if lists[idex] is not None:
    22.                 pg.put((lists[idex].val, idex))
    23.                 lists[idex] = lists[idex].next
    24.         return res.next

    11. 相交链表（两个链表的公共结点）

    160. 相交链表 - 力扣（LeetCode）两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

    a,b分别为两个链表的指针，a走完head1走head2，b走完head2走head1，a和b相遇时即相交。

    1. class Solution:
    2.     def FindFirstCommonNode(self , pHead1 , pHead2 ):
    3.         a , b = pHead1, pHead2
    4.         while a != b:
    5.             # a从pHead1走完，再走pHead2
    6.             if a is not None: a = a.next
    7.             else: a = pHead2
    8.             # b从pHead2走完，再走pHead1
    9.             if b is not None: b = b.next
    10.             else: b = pHead1
    11.         return a
    12. #——————————————简便写法——————————————
    13. class Solution:
    14.     def FindFirstCommonNode(self , pHead1 , pHead2 ):
    15.         a, b = pHead1, pHead2
    16.         while a != b:
    17.             # a从pHead1走完，再走pHead2
    18.             a = a.next if a else pHead2
    19.             # b从pHead2走完，再走pHead1
    20.             b = b.next if b else pHead1
    21.         # 相遇时即为公共结点
    22.         return a

    12. 判断链表中是否有环（环形链表）

    141. 环形链表 - 力扣（LeetCode）

    快慢指针判断

    1. class Solution:
    2.     def hasCycle(self, head: Optional[ListNode]) -> bool:
    3.         if head is None or head.next is None: return False
    4.         fast = slow = head
    5.         while fast and fast.next:
    6.             fast = fast.next.next
    7.             slow = slow.next
    8.             # 注意先走完再判断！
    9.             if fast == slow:
    10.                 return True
    11.         return False

    用 set() 集合存储所有可能性

    1. class Solution:
    2.     def hasCycle(self, head: Optional[ListNode]) -> bool:
    3.         seen = set()
    4.         while head:
    5.             if head in seen:
    6.                 return True
    7.             seen.add(head)
    8.             head = head.next
    9.         return False

    13. 链表中环的入口结点

    快慢指针第一次相遇时停下来。快指针回到head，与慢指针一起走，再次相遇即为环入口。

    1. class Solution:
    2.     def EntryNodeOfLoop(self, pHead):
    3.         if pHead is None: return None
    4.         fast, slow = pHead, pHead
    5.         while fast and fast.next:
    6.             fast = fast.next.next
    7.             slow = slow.next
    8.             # 停在快慢指针相遇的位置
    9.             if slow == fast: break
    10.         # 如果为 None 则表示不存在环
    11.         if fast is None or fast.next is None: return None
    12.  
    13.         # 快指针指向 原head
    14.         fast = pHead
    15.         # 快慢指针同步走，再次相遇时结点为入口结点
    16.         while fast != slow:
    17.             fast = fast.next
    18.             slow = slow.next
    19.         return fast

    set()集合得到入口

    1. class Solution:
    2.     def EntryNodeOfLoop(self, pHead):
    3.         ss =set()
    4.         while pHead:
    5.             if pHead not in ss:
    6.                 ss.add(pHead)
    7.                 pHead = pHead.next
    8.             else:
    9.                 return pHead
    10.         return None

    14. 单链表的排序

    单链表的排序_牛客题霸_牛客网 (nowcoder.com)

    存入数组进行排序

    1. class Solution:
    2.     def sortInList(self , head: ListNode) -> ListNode:
    3.         # 存入数组
    4.         tmp = []
    5.         while head:
    6.             tmp.append(head.val)
    7.             head = head.next
    8.         # 数组排序
    9.         tmp.sort()
    10.         # 构建结果链表
    11.         res = ListNode(-1)
    12.         cur = res
    13.         for i in tmp:
    14.             cur.next = ListNode(i)
    15.             cur = cur.next
    16.         return res.next

    归并排序（递归）

    1. class Solution:
    2.     # 合并两个有序链表
    3.     def merge(self, head1: ListNode, head2: ListNode) -> ListNode:
    4.         if head1 is None: return head2
    5.         if head2 is None: return head1
    6.         res = ListNode(-1)
    7.         cur = res
    8.         while head1 and head2:
    9.             if head1.val <= head2.val:
    10.                 cur.next = head1
    11.                 head1 = head1.next
    12.             else:
    13.                 cur.next = head2
    14.                 head2 = head2.next
    15.             cur = cur.next
    16.         cur.next = head1 if head1 else head2
    17.         return res.next
    18.  
    19.     def sortInList(self , head: ListNode) -> ListNode:
    20.         if head is None or head.next is None: return head
    21.         premid = head
    22.         mid = head.next
    23.         fast = head.next.next
    24.         # 快边指针到达末尾时，中间指针为链表的中间
    25.         while fast and fast.next:
    26.             premid = premid.next
    27.             mid = mid.next
    28.             fast = fast.next.next
    29.         # 左边链表从中间断开
    30.         premid.next = None
    31.         return self.merge(self.sortInList(head), self.sortInList(mid))

    15. 链表的奇偶位置重排

    链表的奇偶重排_牛客题霸_牛客网 (nowcoder.com)

    1. class Solution:
    2.     def oddEvenList(self , head: ListNode) -> ListNode:
    3.         if head is None or head.next is None: return head
    4.         odd = head
    5.         even = head.next
    6.         evenHead = even
    7.         while even and even.next:
    8.             # odd连接偶数位的下一个
    9.             odd.next = even.next
    10.             odd = odd.next
    11.             # even连接奇数位的下一个
    12.             even.next = odd.next
    13.             even = even.next
    14.         odd.next = evenHead
    15.         return head

    16. 删除有序链表中重复的元素

    删除有序链表中重复的元素-I_牛客题霸_牛客网 (nowcoder.com)

    1. class Solution:
    2.     def deleteDuplicates(self , head: ListNode) -> ListNode:
    3.         if head is None or head.next is None: return head
    4.         cur = head
    5.         while cur and cur.next:
    6.             if cur.val == cur.next.val:
    7.                 cur.next = cur.next.next
    8.             else:
    9.                 cur = cur.next
    10.         return head

    17. 删除有序链表中出现重复的元素

    删除有序链表中重复的元素-II_牛客题霸_牛客网 (nowcoder.com)

    1. class Solution:
    2.     def deleteDuplicates(self , head: ListNode) -> ListNode:
    3.         if head is None or head.next is None: return head
    4.         res = ListNode(-1)
    5.         res.next = head
    6.         cur = res
    7.         while cur.next and cur.next.next:
    8.             if cur.next.val == cur.next.next.val:
    9.                 tmp = cur.next.val
    10.                 # 将所有相同的都跳过
    11.                 while cur.next is not None and cur.next.val == tmp:
    12.                     cur.next = cur.next.next
    13.             else:
    14.                 cur = cur.next
    15.         return res.next

  • 相关阅读:
    【Java系列】JDK 1.8 新特性之 Lambda表达式
    PMP每日一练 | 考试不迷路-9.3（包含敏捷+多选）
    Navicat连接openGauss数据库报错
    Vue学习之--------路由的query、params参数、路由命名（3）（2022/9/5）
    如何防止离职员工把企业文件拷贝带走？法律+技术，4步走
    XML、HTML注入和越权问题处理
    c++ 回调函数，std::function，std::bind
    7.4 条件变量示例
    【C++】一篇了解AVL实现细节（易懂图解版）
    前端面试题之最全的操作系统面试题！！
  • 原文地址：https://blog.csdn.net/qq_52057693/article/details/127441702