LeetCode刷题——链表（python语言）

一、链表

1.1 逻辑结构与存储结构

1.1.1 逻辑结构

逻辑结构：数据元素之间的逻辑关系
集合、线性结构（一对一）、树形结构（一对多）、图结构（多对多）

1.1.2 存储结构

存储结构包括顺序存储、链式存储、索引存储、散列存储
顺序存储（顺序表）：逻辑上相邻的元素物理位置也相邻
链式存储（单链表）：逻辑上相邻的元素物理位置不一定相邻

1.2 单链表

1.2.1 单链表的定义

带头节点的单链表（写代码方便）
不带头结点的单链表（写代码麻烦）

class ListNode:def __init__(self,val=0,next=None):self.val = valself.next = next

1.2.2 插入元素

1.2.2.1 带头结点的单链表

头节点在第i个位置插入elem

def Insert(head,i,elem):assert i >= 0 #断言，插入元素的位置必须大于等于0cur = head #指向头指针while(i!=0): #指向插入位置的前一个链表元素i -= 1 cur = cur.nextif not cur:reuturn False #插入位置超出链表长度，返回Falsetemp = cur.next #指向下一位置cur.next = elem #下一位置指向新元素elem.next = temp #元素的末尾指向下一个元素return True

1.2.2.2 不带头节点的单链表

在第i个位置插入elem

def Insert(i,elem): global head #全局变量头指针assert i >=0 #断言，插入元素的位置必须大于等于0if(i==0): #插入的元素在第一个elem.next = head #插入元素的下一位指向头节点head = elem #令该元素为头节点cur = head #记录头节点while(i>1): #插入的元素大于第一个，指向插入位置的前一个链表元素i -= 1cur = cur.nextif not cur:return False #插入位置超出链表长度，返回Falsetemp = cur.next #指向下一位置cur.next = elem #下一位置指向新元素elem.next = temp #元素的末尾指向下一个元素return True

1.2.3 删除元素

def ListDelete(head,i):assert i>=0 #删除的元素位置大于等于0cur = head #记录头节点while(i!=0): #指向删除位置的前一个链表元素i -= 1 cur = cur.nextif not cur.nextreturn False #删除位置超出链表长度，返回Falsecur.next = cur.next.next #将待删除的元素隔过去return True

1.2.4 创建单链表

1.2.4.1 尾插法创建单链表

带头结点的单链表

def BuildLink_Tail(l):if not l: #如果列表为空return None #返回空head = ListNode() #创建头节点temp = head #记录头节点for elem in l:temp.next = ListNode(elem) #当前指向下一个元素temp = temp.next #temo指针后移return headhead = BuildLink_Tail([1,2,3,4])
while head.next: #判断链表是否为空head = head.next #包含头节点所以，先后移print(head.val)

不带头结点的单链表：

def BuildLink_Tail(l):if not l: #如果列表为空return None #返回空head = ListNode(l[0]) #头节点存储第一个元素temp = head #记录头节点for elem in l[1:]: #尾插插入元素temp.next = ListNode(elem)temp = temp.nextreturn headhead = BuildLink_Tail([1,2,3,4])
while head: #当年节点是否为空print(head.val) #没有头节点，先打印head = head.next

1.2.4.2 头插法创建单链表

带头节点的单链表

def BuildLink_Head(l):head = ListNode() #建立头节点for elem in l: #对元素遍历 temp = head.next #存储头节点head.next = ListNode(elem,temp) #头节点后插入新元素return head

不带头结点的单链表

def BuildLink_Head(l):head = None for elem in l:head = ListNode(elem,head) #向头节点后插入元素return head

1.3 双链表

1.3.1 初始化

class DLinkNode:def __init__(self,val=0,next=None,prior):self.val = valself.next = nextself.prior = prior #头指针

1.3.2 作用

解决单链表无法逆向索引的问题

1.4 循环链表

1.4.1 循环单链表

从一个结点出发可以找到其他任何结点

1.4.2 循环双链表

从头到尾和从尾到头时间复杂度都是O（1）

二、 刷题

2.1 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

#解法 直接构建法 创建一个链表，分别对两个链表遍历，取较小值构建链表。当一个链表构建完毕后，直接将另一个链表加入链表后

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeElements(self, head: ListNode, val: int) -> ListNode:head = ListNode(next=head) #建立头节点temp = head #记录头节点while(temp.next !=None): #下一结点为非空if(temp.next.val == val): #下一节点的值是要删除的值temp.next = temp.next.next #删除该节点else:temp = temp.next #否则，指针后移return head.next #带头节点，所以返回头节点的next结点

2.2 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

#解法 循环链表的应用，注意k的优化，和移动的次数(从1开始，长度要加1，做减法要减1)。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:if not head: #没有头节点return None #返回空temp = head #记录头节点length = 0 #长度初始化while(temp.next != None): #下一位置不为空temp = temp.nextlength += 1 #节点长度加一temp.next = head #构建循环链表k = k % (length + 1) #化简ktemp = head #记录头节点for i in range(length-k):#移动头节点temp = temp.nexthead = temp.next #因为legth少加1，所以head指向temp下一节点temp.next = None #将指向头节点的指针为Nonereturn head

2.3 删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

#解法 构建有头的链表，判断下一个结点和下下个结点是否相等。然后记录相等元素，逐一删除。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:if not head: #头节点为空return headdummy = ListNode(0, head) #建立头节点cur = dummy #记录头节点while cur.next and cur.next.next: #next指针和next.next指针if cur.next.val == cur.next.next.val: #相邻的值是否相等x = cur.next.val #x为当前节点的下一个值while cur.next and cur.next.val == x: #当前节点的下一结点不为空，值为xcur.next = cur.next.next #删掉当前节点else:cur = cur.next #结点右移return dummy.next #返回头节点的next结点

2.4 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

#解法 直接构建法 创建一个链表，分别对两个链表遍历，取较小值构建链表。当一个链表构建完毕后，直接将另一个链表加入链表后

# 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]:head = ListNode()temp = head #记录新链表的头节点temp1 = list1 #记录第一个链表的头节点temp2 = list2 #记录第二个链表的头节点while(temp1!= None and temp2!=None): #两个链表都不为空if(temp1.val<temp2.val): #第一个值小于第二个值temp.next = ListNode(temp1.val)  #记录结点temp = temp.next #主链表指针右移temp1 = temp1.next #存储l1的元素，l1指针右移else:temp.next = ListNode(temp2.val) #第一个值大于第二个值temp = temp.next #主链表指针右移temp2 = temp2.next #存储l2的元素，l2指针右移while(temp1!=None):#将没空的链表继续加入主节点temp.next = ListNode(temp1.val) #存储l1的元素，l1指针右移temp = temp.nexttemp1 = temp1.nextwhile(temp2!=None):temp.next = ListNode(temp2.val)temp = temp.nexttemp2 = temp2.nextreturn head.next
#36 ms	15.1 MB
#优点：快速
#缺点：构建链表、程序书写较复杂

2.5 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

解法： 设第一条链表长度为a，第二条链表长度为b，共同的长度为c。
设指针从第一个指针从第一条链表移动后，再从第二条链表移动到相交结点。
a + （b - c)
设指针从第二个指针从第二条链表移动后，再从第一条链表移动到相交结点
b + （a - c)
两条长度相等。
情况1：两指针最终指向相交结点
情况2: 两指针最终指向末尾结点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:A, B = headA, headBwhile A != B: #是否为相交结点A = A.next if A else headB #A指针是否为空B = B.next if B else headA #B指针是否为空return A