上一篇：献芹奏曝-Python面试题
开篇的话：本文目的是收集和归纳力扣上的算法题，希望用python语言，竭我所能做到思路最清奇、代码最简洁、方法最广泛、性能最高效，了解常见题目，找到最利于记忆的答案，更加从容的应对面试。希望广思集益，共同进步。
链表篇
-
237. 删除链表中的节点（难度系数✯）
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteNode(self, node): """ :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. """ node.val = node.next.val node.next = node.next.nextView Code运行结果：1：耗时超过36%。2：内存超过78%
知识点/技巧： 把下一位赋值给当前
-
19. 删除链表的倒数第 N 个结点（难度系数✯）
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: # 1:通过for循环计算列表长度。TODO：可以单独封装成方法 _len = 0 _len_head = head while _len_head: _len += 1 _len_head = _len_head.next pre = head # 删除头结点 if _len-n == 0: return head.next # 找到前一个结点 【1,2,3,4,5】 n=2 for i in range(_len-n-1): pre = pre.next # 让前一个结点的next指向要删除结点的next pre.next = pre.next.next return head方法一运行结果：1：耗时超过55%。2：内存超过93%
知识点/技巧： 通过for循环，计算列表长度。列表长度-N找到待删除的前一个结点
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: slow = head fast = head # 快的先走n步 for i in range(n): fast = fast.next if not fast: # fast 走到末尾了，表示删除首节点 return head.next while fast.next: fast = fast.next slow = slow.next # fast比slow快n步,最后一次fast.next条件成立,fast走到了倒数第二个结点,slow也走到了倒数N+1个结点 slow.next = slow.next.next return head方法二-双指针运行结果：1：耗时超过93%。2：内存超过90%
知识点/技巧： 通过双指针，一个在前，一个在后。前的到头，后面的到达目标位置
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: pos = self.length(head,n) if pos == n: return head.next return head def length(self, head: Optional[ListNode], n: int): if head is None: return 0 pos = self.length(head.next,n)+1 if pos == n+1: head.next = head.next.next return pos方法三-递归运行结果：1：耗时超过8%。2：内存超过93%
知识点/技巧：递归
-
206. 反转链表（难度系数✯）
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next from copy import deepcopy class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head val_list = [] # 暴力反转，先把所有的值放到列表中，再把列表中的值倒着重写组装成列表 while head.next: cur_head = deepcopy(head) cur_head.next = None val_list.append(cur_head) head = head.next new_head = head for item in reversed(val_list): head.next = item head = head.next return new_head暴力反转运行结果：1：超时
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next from copy import deepcopy class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: new_head = None while head: # temp = head.next # 先获取到下一个节点，把它做head节点，从而实现不断while循环 # head.next = new_head # 实现反转 # new_head = head # head = temp head.next,new_head,head =new_head, head,head.next return new_head双链表求解 一行代码运行结果：1：耗时超过66%。2：内存超过76%
知识点/技巧：把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next from copy import deepcopy class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head reverse = self.reverseList(head.next) head.next.next = head head.next = None return reverse递归调用运行结果：1：耗时超过99.06%。2：内存超过8.89%
知识点/技巧：递归调用之后head.next节点就会成为reverse节点的尾结点，我们可以直接让head.next.next = head;
- 21. 合并两个有序链表（难度系数✯）
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() move = dummy while list1 and list2: if list1.val < list2.val: move.next = list1 list1 = list1.next else: move.next = list2 list2 = list2.next # 每次比完，移动一位 move = move.next move.next = list1 if list1 else list2 return dummy.next方法一运行结果：1：耗时超过42%。2：内存超过49%
知识点/技巧：取最小数据添加到当前节点后面
- 141. 环形链表 （难度系数✯）
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if not head: return False fast = head slow = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True else: # 有尽头，所以不为环 return False快慢指针运行结果：1：耗时超过76%。2：内存超过71%
知识点/技巧：慢指针针每次走一步，快指针每次走两步，如果相遇就说明有环，如果有一个为空说明没有环。类似钟表上的分针与秒针
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: i=0 while head and head.next and i<10**4+1 : head = head.next i += 1 else: return i>10**4暴力破解运行结果：1：耗时超过31%。2：内存超过31%
知识点/技巧：根据题意，设置10**4为边界。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: set_result = set() while head: if head in set_result: return True else: set_result.add(head) head = head.next else: return Falseset集合运行结果：1：耗时超过90%。2：内存超过80%
知识点/技巧：利用set集合判断，其实list也可以。
标签：面试题,ListNode,val,Python,self,head,next,链表,def From： https://www.cnblogs.com/YK2012/p/16573028.html