内容简介：链表（LikedList）是线性表（Linear List）的一种，是一种非常常见
链表（LikedList）是线性表（Linear List）的一种，是一种非常常见 数据结构 ，链表通过指针将一组零散的内存块串联在一起，通过不同的串联方式形成不同类型的链表结构，最常见有单链表、双链表和循环链表。
目录
1. 基础知识要点
链表的类型
-
单链表
-
双链表
从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱节点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
-
循环链表
-
双向循环链表
2. 常用方法和注意事项
链表本身并不复杂，但是非常容易出错，做题时一定要注意细节，多画图多举例，下面是链表问题代码实现的常用方法以及注意事项。
-
关键节点指针的临时复制
头节点、尾节点以及中间动态扫描的节点，通常会用作返回节点或链接其他节点，所以经常会使用赋值操作来复制关键节点的指针（确切而言，指针在 Python 中称为引用），或者动态调整指针所指向的节点位置，来辅助完成所需操作。这个过程相当于给节点所对应的内存地址保存了一份记录点，当再次用到该节点的时候可以随时调取。
-
快指针和慢指针
快慢指针的方法是构造一种位置上的相对差异，然后利用这种位置差异来完成一些特殊操作。
-
虚拟头（也称哨兵节点）
虚拟头可以免去一些边界条件的特殊处理，需注意虚拟头节点返回的是它的next节点而不是本身。
-
注意边界条件的处理
链表题非常容易出错的地方就是容易忽略边界条件讨论处理，常需要注意的边界条件有：空节点、头节点、尾节点、长度为1或2的链表。
3. 反转链表（LC92.Medium）
题目：
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
思路：
方法一：
一个比较普通的思路是分为三部分（反转前段、反转段、反转后段），分别完成三部分再拼接，因为可能存在 m=1 的情况，返回头节点也会不同，还需要特殊讨论，这种方法略繁琐。
方法二：
加入虚拟头节点，可免去讨论 m=1 的情况，然后将整个过程看成依次把反转段后面的一个节点拿到反转段最前面去，以示例为例：
到反转段继续扫描节点，依次将指针后面的节点调整到前面（ range(m, n) ）或可理解为调整两次（ range(n-m) ）： 第一次，把3调整到反转段最前面，重新调整指向，此时为：
dummyNode->1->3->2->4->5->NULL
第二次，把4调整到反转段最前面，重新调整指向，此时为：
dummyNode->1->4->3->2->5->NULL
反转段代码实现部分用到了Python的多元赋值，这个多元赋值在反转问题经常使用，可巧妙利用多元赋值右面的值不会随着赋值操作而改变，如单链表反转可以十分简单地用多元赋值实现：
pre = None while head: # 每次完成三个任务：变更指向，移动pre指针，移动head指针 head.next, pre, head = pre, head, head.next return pre
但是需要注意的是，多元赋值左边是会改变的，一定要注意赋值顺序，所以上面的多元赋值部分不能写成：
# 此时第一个head已经改变 ，第二个head.next实际上成了head.next.next head，head.next, p = head.next，p, head
代码：
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseBetween(self, head, m, n): """ :type head: ListNode :type m: int :type n: int :rtype: ListNode """ dummyNode = ListNode(0) dummyNode.next = head pre = dummyNode # 先将链表指针移动到反转部分的前一个节点，也就是pre # pre前面的一部分是不动的 for _ in range(m - 1): pre = pre.next # 复制指针，指向反转部分的头节点，作为初始head head = pre.next # 反转部分，以head为锚点，依次往后扫描 # （实际上遍历的是nex，每次都是把nex扔到反转段的第一个，所以遍历n-m次） for _ in range(m, n): # 依次调整每一个nex nex = head.next # 依次改变指向，循环遍历，注意随着调整，每一个变量都是动态的 pre.next, head.next, nex.next = nex, nex.next, pre.next return dummyNode.next
4. 相交链表求交点（LC160.Easy）
题目：
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表 ：
在节点 c1 开始相交。
示例 1：
输入：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 个节点。
示例 2：
输入：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 个节点。
示例 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。
注意：
-
如果两个链表没有交点，返回
null. -
在返回结果后，两个链表仍须保持原有的结构。
-
可假定整个链表结构中没有循环。
-
程序尽量满足 O( n ) 时间复杂度，且仅用 O( 1 ) 内存。
思路:
方法一（M1）：
利用set集合，时间复杂度O(nlogn) （因为用了set集合），空间复杂度O(n)。
遍历第一个链表，将每一个节点存入set集合，然后遍历第二个链表，判断当前节点是否存在与set集合，存在则证明该节点是相交节点，直接返回，若遍历完整个链表都没有，则返回 None ，表明两个链表不相交。
方法二（M2，Best）：
时间复杂度O(n) ，空间复杂度O(1)。
先分别遍历两个链表，获知两个链表各自的长度，往后调整较长链表的指针，使之与较短链表的起始指针对齐，然后两个链表同时往后扫描，直至二者的节点相同，证明该节点是相交节点，否则返回 None ，表明两个链表不相交。
代码：
# 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 """ # M1， T：O(nlogn) S:O(n) # A_set = set() # while headA: # A_set.add(headA) # headA = headA.next # while headB: # # print headB # if headB in A_set: # return headB # headB = headB.next # return None # M2, Best T:O(n), S:O(1) def get_list_length(head): len = 0 while head: len +=1 head = head.next return len def forward_long_list(long_len, short_len, head): delta = long_len - short_len while head and delta: head = head.next delta -= 1 return head def main(headA, headB): headA_len = get_list_length(headA) headB_len = get_list_length(headB) if headA_len > headB_len: headA = forward_long_list(headA_len, headB_len, headA) else: headB = forward_long_list(headB_len, headA_len, headB) while headA and headB: if headA == headB: return headA headA = headA.next headB = headB.next return None return main(headA, headB)
5. 链表求环(LC142.Medium)
题目：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null 。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1 ，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。
进阶：你是否可以不用额外空间解决此题？
思路：
方法一（M1）：
利用set()集合，时间复杂度O(n) ，空间复杂度O(n)。
非常简单，遍历链表存入set集合中，第一次遇到重复的就是入环节点，不过这种方法使用了额外空间。
方法二（M2，Best）：
使用快慢指针，快指针每次走两步，慢指针每次走一步，这里有些数学技巧，通过分析最后得出，从头节点 head 到入环节点和从相遇节点 meet 到入环节点的距离是一样的。所以，先找到快慢指针的相遇节点，然后同时从头节点和相遇节点遍历，直到二者的节点相同，则证明该节点是入环节点。
# 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 """ # M1, use set # node_set = set() # while head: # if head in node_set: # return head # node_set.add(head) # head = head.next # return None # M2, fast and slow pointer fast = head slow = head meet = None while fast: slow = slow.next fast = fast.next if not fast: return None fast = fast.next if fast == slow: meet = slow break if not meet: return None while head and meet: if head == meet: return head head = head.next meet = meet.next return None
6. 链表划分（LC86.Medium）
题目：
给定一个链表和一个特定值 x ，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
思路：
这道题的思路很简单，借助两个虚拟头节点分成两个部分，然后扫描节点分别划分到不同的部分，划分完再拼接，有些类似的题还有等于的情况，也是类似的处理方法，也就是分三段拼接。
代码：
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def partition(self, head, x): """ :type head: ListNode :type x: int :rtype: ListNode """ # 这个题不用管等于的情况，也就是等于不用往前移动，分两段就可以了 less_head = ListNode(0) more_head = ListNode(0) less_ptr = less_head more_ptr = more_head while head: if head.val < x: less_ptr.next = head less_ptr = head else: more_ptr.next = head more_ptr = head head = head.next less_ptr.next = more_head.next more_ptr.next = None return less_head.next
7. 链表求中间节点（LC876.Easy）
题目：
给定一个带有头节点 head 的非空单链表，返回链表的中间节点。
如果有两个中间节点，则返回第二个中间节点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的节点 3 (序列化形式：[3,4,5]) 返回的节点值为 3 。 (测评系统对该节点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的节点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间节点，值分别为 3 和 4，我们返回第二个节点。
提示：
- 给定链表的节点数介于
1和100之间。
思路：
方法一：
利用数组（Python中的列表），时间复杂度O(N)，空间复杂度O(N)；
按顺序将每个节点放入数组 A 中。然后中间节点就是 A[A.Length/2] ，因为我们可以通过索引检索每个节点。
方法二：
当用慢指针 slow 遍历链表时，让另一个指针 fast 的速度是它的两倍。
当 fast 到达链表的末尾时， slow 必然位于中间。
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def middleNode(self, head): """ :type head: ListNode :rtype: ListNode """ # M1，@official，use List，T:O(n) S:O(n) # A = [head] # while A[-1].next: # A.append(A[-1].next) # return A[len(A) / 2] #M2 @official, Fast And Slow Pointer, T:O(n) S:O(1) slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow
8. 删除链表倒数第n个节点（LC19.Medium）
题目：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
思路：
利用快慢指针，定位倒数 n+1 节点位置。快指针 fast 先走 n+1 步，然后快慢指针一同遍历，当快指针 fast 到达链表末尾时，慢指针 slow 必然位于倒数 n+1 节点的位置（慢指针与快指针差 n+1 步，当快指针到达链表末尾，也就意味着慢指针与链表末尾的距离是 n+1 步），然后调整该节点指向该节点的下下一个指针（倒数 n-1 节点），完成删除导数 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 """ dummy = ListNode(0) dummy.next = head slow, fast = dummy, dummy for _ in range(n + 1): fast = fast.next while fast: slow = slow.next fast = fast.next slow.next = slow.next.next return dummy.next
9. 复杂链表的复制（LC138.Medium）
题目：
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝 。
示例：
输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
提示：
- 你必须返回 给定头的拷贝 作为对克隆列表的引用。
思路：
本题的关键在于随机指针的指向，需要额外的存储空间记录随机指针的相对关系，这里主要借助字典（哈希表）来记录新旧链表各个对应节点的映射。
代码：
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, next, random):
self.val = val
self.next = next
self.random = random
"""
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if not head:
return None
dummy = Node(0,None,None)
# 复制两个指针，用于扫描原链表和构建新链表
new_ptr = dummy
src_ptr = head
# 初始化一个字典，
node_map = {} #key: src_node, value: new_node
# 构建新链表并存储新旧链表各自节点的地址映射
while src_ptr:
new_ptr.next = Node(src_ptr.val,None,None)
new_ptr = new_ptr.next
node_map[src_ptr] = new_ptr
src_ptr = src_ptr.next
# 再次扫描，对新链表random赋值
new_ptr = dummy.next
src_ptr = head
while src_ptr:
if src_ptr.random:
new_ptr.random = node_map[src_ptr.random]
src_ptr, new_ptr = src_ptr.next, new_ptr.next
return dummy.next
10. 有序链表的合并(LC23.Hard)
题目
合并 k 个 排序 链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
思路：
方法一（M1）：
将所有列表的所有节点都放置在一个额外的列表中，然后对这个列表排序，为了方便返回最小的头节点，这里使用降序排序，然后将这些节点由大到小，由右及左的顺序链接到一起，最后一个节点便是最小的头节点。
时间复杂度分析：使用 sorted() 函数排序，Python的内置函数 sorted() 底层实现是归并排序，时间复杂度是O(nlogn)，设有 k 个链表，每个链表有 n 个节点，因此共有 kn 个节点需要排序，所以第一种方法的时间复杂度是O(kn*log kn)。
方法二（M2，Best）：
分治法和递归法，每两个链表合并一个，然后再次两两合并，通过递归完成所有链表的合并。
时间复杂度分析：设有 k 个链表，每个链表有 n 个节点
第1轮：进行k/2次，每次处理2n个数字；
第2轮：进行k/4次，每次处理4n个数字；
……
最后一轮：进行$k/(2^{\log k})$次，每次处理$2^{\log k} *n$个值。
则有$2n*k/2 + 4n*k/4+8n*k/8+\cdots+2^{\log k}*n*k/(2^{\log k})=kn+kn+kn+\cdots+kn=O(kn\log k)$，
所以第二种方法的时间复杂度是O(kn*log k)。
代码：
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ # M1, Sorted() node_list = [] for li in lists: head = li while head: node_list.append(head) head = head.next if node_list: sorted_node_list = sorted(node_list, key=lambda x: x.val, reverse=True) else: return None p = None for n in sorted_node_list: n.next, p = p, n return n # # M2, 分治法 和 递归法 # if not lists: return # n = len(lists) # return self.merge(lists, 0, n-1) # def merge(self,lists, left, right): # if left == right: # return lists[left] # mid = left + (right - left) // 2 # l1 = self.merge(lists, left, mid) # l2 = self.merge(lists, mid+1, right) # return self.mergeTwoLists(l1, l2) # def mergeTwoLists(self,l1, l2): # if not l1:return l2 # if not l2:return l1 # if l1.val < l2.val: # l1.next = self.mergeTwoLists(l1.next, l2) # return l1 # else: # l2.next = self.mergeTwoLists(l1, l2.next) # return l2 # # 下面是两个链表合并的更加抽象的一种写法，原理实际与上面的一样。 # # if l1 and l2: # # if l1.val > l2.val: l1, l2 = l2, l1 # # l1.next = self.mergeTwoLists(l1.next, l2) # # return l1 or l2
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 图算法|Dijkstra算法python实现
- 算法：经典排序算法的 Go 实现
- js实现数据结构及算法之排序算法
- 算法 - 06 | 链表（上）：如何实现LRU缓存淘汰算法?
- Twitter雪花算法SnowFlake算法的java实现
- js实现多种排序算法（算法导论第二章）
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
游戏编程权威指南
Mike McShaffry 麦克沙福瑞、David “Rez” Graham 格雷海姆 / 师蓉、李静、李青翠 / 人民邮电 / 2016-3 / 99.00元
全书分为4个部分共24章。首部分是游戏编程基础，主要介绍了游戏编程的定义、游戏架构等基础知识。 第二部分是让游戏跑起来，主要介绍了初始化和关闭代码、主循环、游戏主题和用户界面等。 第三部分是核心游戏技术，主要介绍了一些*为复杂的代码 示例，如3D编程、游戏音频、物理和AI编程等。 第四部分是综合应用，主要介绍了网络编程、多道程序设计和用C#创建工具等，并利用前面所讲的 知识开发出......一起来看看 《游戏编程权威指南》 这本书的介绍吧!
