刷题中的链表总结(持续跟新)

剑指offer18-删除链表节点

class Solution: def deleteNode(self, head: ListNode, val: int) -> ListNode: if head.val == val: return head.next pre, cur = head, head.next while cur and cur.val != val: pre, cur = cur, cur.next if cur: pre.next = cur.next return head

反转链表

注意： 链表问题伴随着大量指针操作。面试时不要急着写代码，仔细分析设计不容易出错。 由于链表是不连续存储的。当调节节点i的next指针时，需要（这里用tmp）来保存后节点的位置 常见错误： ① 输入链表头指针为null（特殊输入测试）或只有一个节点（一个功能测试）时，程序崩溃 ②反转链表出现断裂 ③返回的头节点不是原始链表的尾节点 解决方法： 提前想好测试用例，心中默默运行代码进行单元测试，再交给面试官

双指针循环解法**

# # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): if not pHead or not pHead.next:# 判断特殊情况，链表为空或者只有一个node return pHead pre = None cur = pHead next = pHead.next while cur:# 注意这个地方是cur,还是cur.next，心中跑完代码再写 tmp = cur.next cur.next = pre pre = cur cur = tmp return pre

递归方法 递归方法我总是是是而非的，没有用一个时间段来用递归方法做题

class Solution: # 返回ListNode def ReverseList(self, pHead): if not pHead or not pHead.next: return pHead pNew = self.ReverseList(pHead.next) pHead.next.next = pHead pHead.next = None return pNew

两链表的第一个公共节点

思路： hashmap可以解决不是面试官想要的思路，暴力时间复杂度O(MN) 双指针 第二种双指针好好看看！！！ 创建两个指针p1和p2,分别指向两个链表的头结点，然后依次往后遍历。如果某个指针到达末尾，则将该指针指向另一个链表的头结点；如果两个指针所指的节点相同，则循环结束，返回当前指针指向的节点。比如两个链表分别为：1->3->4->5->6和2->7->8->9->5->6。短链表的指针p1会先到达尾部，然后重新指向长链表头部，当长链表的指针p2到达尾部时，重新指向短链表头部，此时p1在长链表中已经多走了k步(k为两个链表的长度差值)，p1和p2位于同一起跑线，往后遍历找到相同节点即可。其实该方法主要就是用链表循环的方式替代了长链表指针先走k步这一步骤

class Solution:# 傻逼双指针 def FindFirstCommonNode(self, pHead1, pHead2): if not pHead1 or not pHead1.next or not pHead2 or not pHead2.next: return None length1 = 1 length2 = 1 tmp = 0 cur1 = pHead1 cur2 = pHead2 while cur1: cur1 = cur1.next length1 += 1 while cur2: cur2 = cur2.next length2 += 1 if length1 > length2: while tmp < length1 - length2: pHead1 = pHead1.next tmp += 1 if length1 <= length2: while tmp < length2 - length1: pHead2 = pHead2.next tmp += 1 while pHead1: if pHead1.val == pHead2.val and pHead1.next == pHead2.next: return pHead1 else: pHead1 = pHead1.next pHead2 = pHead2.next return None ```python# 巧妙精简化的双指针 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindFirstCommonNode(self, pHead1, pHead2): if not pHead1 or not pHead1.next or not pHead2 or not pHead2.next: return None p1 = pHead1 p2 = pHead2 while p1 != p2: p1 = p1.next if p1 else pHead2 p2 = p2.next if p2 else pHead1 return p1

链表中环的入口结点

hashmap

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def EntryNodeOfLoop(self, pHead): li = []# 刚开始我用的list命名：不能与关键词重合！ p = pHead if not p or not p.next: return None while pHead: if pHead in li:# 列表查找O(N),所以这里换成dict 或者 set # if pHead in dict: # return pHead # else: # dict[pHead] = 1 # pHead = pHead.next #return pHead else: li.append(pHead)# 是将pHead这个节点存到li中，而不是仅仅将pHead.val这个元素 pHead = pHead.next return None class Solution:# 用set def EntryNodeOfLoop(self, pHead): s = set([]) while pHead: if pHead in s: return pHead else: s.add(pHead) pHead = pHead.next return None

快慢指针 思路：slow每次走一步，fast每次走两步 ① 判断是否有环：如果slow追上fast(相遇)有环 ② 找入口：让slow从相遇点出发，新指针从pHead出发，每次走一步，相遇即是入口（证明自己找找）

class Solution: def EntryNodeOfLoop(self, pHead): slow,fast = pHead,pHead while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: slow2 = pHead while slow != slow2:# 新指针从pHead出大 slow = slow.next slow2 = slow2.next return slow return None

合并两个排序链表

双指针 注意！ tmp = ListNode(0) return pHead.next

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): tmp = ListNode(0) pHead = tmp while pHead1 and pHead2:# 注意 if pHead1.val < pHead2.val: tmp.next = pHead1 pHead1 = pHead1.next else: tmp.next = pHead2 pHead2 = pHead2.next tmp = tmp.next if not pHead1: tmp.next = pHead2 if not pHead2: tmp.next = pHead1 return pHead.next

链表中倒数第K个节点

注意： ① 链表头节点为空指针 ② 链表节点数小于k ③ k=0

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def kthToLast(self, head: ListNode, k: int) -> int: if not head or k < 0: return None a = head b = head for i in range(k): if not b: return None b = b.next while b: a = a.next b = b.next return a.val