本文最后更新于 566 天前,其中的信息可能已经有所发展或是发生改变。
单链表
表域元素val
保存着数据项,链接域next
保存同一表里的下个节点的标识,P
为表头变量/表头指针
插入新元素
- 初始化新节点
cur
- 将
cur
的next
字段链接到prev
的下个节点 - 将
prev
中的next
字段链接到cur
在开头插入节点
- 初始化一个新节点
cur
- 将新节点链接到原始头结点
head
- 将
cur
指定为head
删除操作
- 找到
cur
的上一个结点prev
及其下一个结点next
-
链接
prev
到cur
的下一个结点next
在第一步中,要找到prev
和next
,需要从头结点开始遍历链表,才能找到prev
,平均时间复杂度是$O(n)$
删除第一个节点
- 给定原始链表和头结点
head
-
将头结点的下个节点指定为头结点
head
单链表操作的复杂度
- 创建链表:$O(1)$
- 删除链表:在python里是$O(1)$
- 判断表空:$O(1)$
- 首端加入元素:$O(1)$
- 尾端加入元素,要找到表的最后节点:$O(n)$
- 定位插入元素:$O(n)$
- 首端删除元素:$O(1)$
- 尾端删除元素:$O(n)$
- 定位删除元素:$O(n)$
- 扫描、定位、遍历:$O(n)$
循环单链表
在链表对象里记录尾节点,这样可以同时支持$O(1)$的表头/表尾插入和$O(1)$的表头删除
双链表
双链表除了next
字段,还有一个prev
字段,指向当前节点的前一个节点
添加操作
- 初始化一个新节点
cur
- 链接
cur
与prev
的next
,链接cur
的prev
与prev
- 用
cur
重新链接prev
和next
删除操作
循环双链表
代码实现
单链表
单链表中的节点应该具有两个属性:val
和 next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。假设链表中的所有节点都是 0-index 的。在链表类中实现这些功能:
- get(index):获取链表中第
index
个节点的值。如果索引无效,则返回-1
。 - addAtHead(val):在链表的第一个元素之前添加一个值为
val
的节点。插入后,新节点将成为链表的第一个节点。 - addAtTail(val):将值为
val
的节点追加到链表的最后一个元素。 - addAtIndex(index,val):在链表中的第
index
个节点之前添加值为val
的节点。如果index
等于链表的长度,则该节点将附加到链表的末尾。如果index
大于链表长度,则不会插入节点。 - deleteAtIndex(index):如果索引
index
有效,则删除链表中的第index
个节点。
# 节点类,代表链表的每个节点
class Node(object):
def __init__(self, x, next_=None):
# 节点的值
self.val = x
# 节点的下个指向
self.next = next_
# 链表类
class MyLinkedList(object):
# 初始化
def __init__(self):
# 初始化头部节点
self.head = None
# 记录链表长度
self.length = 0
# 打印链表所有节点
def print_all(self):
p = self.head
res = []
res.append(p.val)
while p.next:
p = p.next
res.append(p.val)
print(res)
# 根据索引index获得节点
def get(self, index):
'''
获得第index个节点
'''
# 头部节点
p = self.head
# 若链表为空或index小于0,则返回-1
if not p or index < 0:
return -1
# 遍历链表找到第index个节点
while index >= 1:
# 若index大于链表长度
if p.next == None:
return -1
else:
p = p.next
index -= 1
return p.val
def addAtHead(self, val):
'''
在头部添加节点
'''
# 新建值为val的节点,next指向head节点的next,然后将此节点指定为head节点
self.head = Node(val, self.head)
self.length += 1
def addAtTail(self, val):
'''
在尾部添加节点
'''
# 如果链表为空,则在头部添加节点
if self.head == None:
self.head = Node(val)
self.length += 1
return
# 链表不为空,先获得头部节点
p = self.head
# 遍历节点,找到最后一个节点
while p.next is not None:
p = p.next
# 最后一个节点指向新建节点
p.next = Node(val)
self.length += 1
def addAtIndex(self, index, val):
'''
在第index插入节点。若index等于链表长度,则在尾部添加,若大于节点长度,则节点不会被插入
'''
# 若index等于链表长度,节点添加为尾部
if index == self.length:
self.addAtTail(val)
# 若index==0,节点添加在头部
elif index == 0:
self.addAtHead(val)
# 若index大于链表长度或为负,不插入节点
elif index + 1 > self.length or index < 0:
return
else:
p = self.head
# 获得插入位置的前一个节点
while index > 1:
index -= 1
p = p.next
# 新建当前节点,next指向前一个节点的next
cur = Node(val, p.next)
# 前一个节点的next指向当前节点
p.next = cur
self.length += 1
def deleteAtIndex(self, index):
'''
删除第index个节点
'''
# 若index大于链表长度或为负,不删除节点
if index + 1 > self.length or index < 0:
return
# 若index==0,删除头部节点
elif index == 0:
# 重新指定头部节点为当前头部的next
self.head = self.head.next
self.length -= 1
return
else:
p = self.head
# 获得指定位置的前一个节点
while index > 1:
p = p.next
index -= 1
# 若前一个节点不为倒数第二个节点(也就是删除除头结点、尾节点以外的中间节点)
if p.next.next is not None:
p.next = p.next.next
# 若指定位置的前一个节点为倒数第二个节点(也就是删除尾节点)
else:
p.next = None
self.length -= 1
双指针应用
判断环形链表
给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos
是 -1
,则在该链表中没有环。
示例1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
'''
:type head: ListNode
:rtype: bool
'''
'''
# 方法一 双链表
p1 = p2 = head
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
return True
return False
'''
### 方法二 哈希表
if head==None:
return False
hash_table=set()
q=head
while head:
if head in hash_table:
return True
else:
hash_table.add(head) ##set 没有append 只有add
head=head.next
return False
环形链表(二)
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。为了表示给定链表中的环,我们使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos
是 -1
,则在该链表中没有环。说明:不允许修改给定的链表。
示例一:
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。
示例二:
输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。
示例三:
输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
'''
:type head: ListNode
:rtype: ListNode
'''
p1 = p2 = head
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
p = head
while p != p1:
p = p.next
p1 = p1.next
return p
return None
相交链表
编写一个程序,找到两个单链表相交的起始节点。
示例一:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例二:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例三:
输入: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。
注意:
- 如果两个链表没有交点,返回
null
. - 在返回结果后,两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 $O(n)$ 时间复杂度,且仅用 $O(1)$ 内存。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
'''
:type head1, head1: ListNode
:rtype: ListNode
'''
'''
# 方法一 哈希表
pa, pb = headA, headB
table = set()
while pa:
if pa not in table:
table.add(pa)
pa = pa.next
while pb:
if pb in table:
return pb
pb = pb.next
return None
'''
# 方法二 双指针
pA = headA
pB = headB
while pA != pB:
pA = pA.next if pA is not None else headB
pB = pB.next if pB is not None else headA
return pA
删除链表的导数第N个节点
给定一个链表,删除链表的倒数第 $n$ 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 $n$ 保证是有效的。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
'''
:type head: ListNode
:type n: int
:rtype: ListNode
'''
'''
p = head
length = 0
table = []
while p:
table.append(p)
length += 1
p = p.next
if n == 1:
if length == 1:
return None
else:
table[-n-1].next = None
return head
if n == length:
return table[-n+1]
table[-n-1].next = table[-n-1].next.next
return head
'''
#构建双指针p1与p2,p1先走n步,然后一同运动,当p1指向表尾,p2指向的next即是倒数第N个节点,删除即可。
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for i in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
参考资料
- https://leetcode-cn.com/explore/learn/card/linked-list/
- 《数据结构与算法:Python语言描述》