简介 - 单链表
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。、
下面是一个单链表的例子：
正如你所看到的，链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。
链表有两种类型：单链表和双链表。上面给出的例子是一个单链表，这里有一个双链表的例子：
我们将在接下来的章节中介绍更多内容。完成这张卡片后，你将：
- 了解单链表和双链表的结构；
- 在单链表或双链表中实现遍历、插入和删除；
- 分析在单链表或双链表中的各种操作的复杂度；
- 在链表中使用双指针技巧（快指针慢指针技巧）；
- 解决一些经典问题，例如反转链表；
- 分析你设计的算法的复杂度；
- 积累设计和调试的经验。
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。、
下面是一个单链表的例子：
蓝色箭头显示单个链接列表中的结点是如何组合在一起的。
在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
操作
与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。
例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。
你可能想知道为什么链表很有用，尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 在接下来的两篇文章中，我们将介绍插入和删除操作，你将了解到链表的好处。
如果我们想在给定的结点 prev 之后添加新值，我们应该：
- 使用给定值初始化新结点
cur；
- 将
cur的“next”字段链接到 prev 的下一个结点next；
- 将
prev中的“next”字段链接到cur。
与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。
示例
让我们在第二个结点 6 之后插入一个新的值 9。
我们将首先初始化一个值为 9 的新结点。然后将结点 9 链接到结点 15。最后，将结点 6 链接到结点 9。
插入之后，我们的链表将如下所示：
在开头添加结点
众所周知，我们使用头结点来代表整个列表。
因此，在列表开头添加新节点时更新头结点 head 至关重要。
- 初始化一个新结点
cur； - 将新结点链接到我们的原始头结点
head。 - 将
cur指定为head。
例如，让我们在列表的开头添加一个新结点 9。
- 我们初始化一个新结点 9 并将其链接到当前头结点 23。
- 指定结点 9 为新的头结点。
如何在列表的末尾添加新的结点？我们还能使用类似的策略吗？
如果我们想从单链表中删除现有结点 cur，可以分两步完成：
- 找到 cur 的上一个结点
prev及其下一个结点next；
2. 接下来链接 prev 到 cur 的下一个节点 next。
在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。
空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。
示例
让我们尝试把结点 6从上面的单链表中删除。
1. 从头遍历链表，直到我们找到前一个结点 prev，即结点 23
2. 将 prev（结点 23）与 next（结点 15）链接
结点 6 现在不在我们的单链表中。
删除第一个结点
如果我们想删除第一个结点，策略会有所不同。
正如之前所提到的，我们使用头结点 head 来表示链表。我们的头是下面示例中的黑色结点 23。
如果想要删除第一个结点，我们可以简单地将下一个结点分配给 head。也就是说，删除之后我们的头将会是结点 6。
链表从头结点开始，因此结点 23 不再在我们的链表中。
删除最后一个结点呢？我们还能使用类似的策略吗？
链表中的双指针
让我们从一个经典问题开始：
给定一个链表，判断链表中是否有环。
你可能已经使用哈希表提出了解决方案。但是，使用双指针技巧有一个更有效的解决方案。在阅读接下来的内容之前，试着自己仔细考虑一下。
想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。
这正是我们在链表中使用两个速度不同的指针时会遇到的情况：
如果没有环，快指针将停在链表的末尾。
如果有环，快指针最终将与慢指针相遇。
所以剩下的问题是：
这两个指针的适当速度应该是多少？
一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。
那其他选择呢？它们有用吗？它们会更高效吗？
环形链表 给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
# 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 """ # 使用追逐法(双指针),fast每次走两步,slow每次走一步 if head==None or head.next==None: return False fast=head.next slow=head while fast!=None: if fast==slow: return True fast=fast.next if fast==None: return False fast=fast.next slow=slow.next return False
环形链表 II 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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 解释：链表中没有环。
https://blog.csdn.net/Sun_White_Boy/article/details/82845791?utm_source=blogxgwz3 # 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 """ if head == None or head.next == None: return None slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: tmp = head while tmp != fast: tmp,fast = tmp.next,fast.next return tmp return None
# 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 """ #思路:利用set进行存储head节点对象(地址),当地址重复时,即遇到重复环 head_set=set() while head: if head in head_set: return head else: head_set.add(head) head=head.next return None
相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 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。
# 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 """ # 思路:与上一题相似,利用set进行存储A每个节点的地址,通过遍历B,当节点存在是,return其节点的取值 headA_set=set() while headA: headA_set.add(headA) headA=headA.next while headB: if headB in headA_set: return headB headB=headB.next return None
删除链表的倒数第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 # 使用前后索引(双索引)，这个的写法是，用一条像是绳子一样的。 # |----------| # slow fast # 让fast走n步。 # 然后fast和slow一起走，等fast.next是None，也就是到头了。那么slow就是要删除的点的前一个了。 # 直接把slow.next与slow.next.next结合就达标了。 # 如果走了n步后fast直接是None了。那么说明删除的节点是head，那么返回 head.next就好了。
""" first=head tail=head while first: #表明tail 与first之间的距离达到了n,且tail.next==None,表明first的下一位为要删除的元素 if tail.next==None and n==0: first.next=first.next.next return head #n!=0,表明该没有tail与first之间的距离还没有达到n,就停止了,head已经遍历完,那么其删除的元素为其第一个元素 elif tail.next==None and n!=0: return head.next #tail与first之间间距为n if n!=0: tail=tail.next n-=1 continue #满足间距之后,first与tail一起移动 first=first.next tail=tail.next return None
反转链表
一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部。似乎很难理解。我们先用一个例子来说明我们的算法
算法概述
让我们看一个例子：
请记住，黑色结点 23 是原始的头结点。
1. 首先，我们将黑色结点的下一个结点（即结点 6）移动到列表的头部：
2. 然后，我们将黑色结点的下一个结点（即结点 15）移动到列表的头部：
3. 黑色结点的下一个结点现在是空。因此，我们停止这一过程并返回新的头结点 15。
在该算法中，每个结点只移动一次。
因此，时间复杂度为 O(N)，其中 N 是链表的长度。我们只使用常量级的额外空间，所以空间复杂度为 O(1)。
反转链表 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ # 迭代的方法 prev = None while head: cur = head head = head.next cur.next = prev prev = cur return prev
移除链表元素 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def removeElements(self, head, val): """ :type head: ListNode :type val: int :rtype: ListNode """ # 思路:删除头结点为val的节点(保证上一个节点不等于val),这样好进行下面删除的操作.记录上一个节点为prev,记录当前节点为cur,进行判断,如果cur.val与val相等,则利用上一个节点连接当前节点的下一个节点. if head is None : return None while head.val == val: head = head.next if head is None: return None prev = head cur = head.next while cur != None: if cur.val == val: cur = cur.next prev.next = cur else: prev, cur = cur, cur.next return head
奇偶链表 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。 示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2: 输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL 说明: 应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def oddEvenList(self, head): """ :type head: ListNode :rtype: ListNode """ #思路:将链表分为两部分,最后进行连接 if head == None or head.next == None: return head slow=head fast=head.next t=fast #得保证两者的下一位都不为None,否则,会出现,None.next while slow.next and fast.next: slow.next=fast.next slow=slow.next fast.next=slow.next fast=fast.next slow.next=t return head
回文链表 请判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ # 思路:遍历链表,使用list存储,if not head : return True temp_list=[] while head: temp_list.append(head.val) head=head.next return temp_list==temp_list[::-1]
合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ new_head=ListNode(0) pre=new_head while l1 and l2: if l1.val<=l2.val: pre.next=l1 l1=l1.next else: pre.next=l2 l2=l2.next pre=pre.next if l1==None: pre.next=l2 if l2==None: pre.next=l1 return new_head.next
两数相加 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ #思路:将链表转化为list进行操作 int_l1='' int_l2='' while l1: int_l1+=str(l1.val) l1=l1.next while l2: int_l2+=str(l2.val) l2=l2.next int_l1=int(int_l1[::-1]) int_l2=int(int_l2[::-1]) sum_=(int_l1+int_l2) nu=sum_%10 sum_=sum_/10 k=ListNode(nu) head=k while sum_: nu=sum_%10 sum_=sum_/10 head.next=ListNode(nu) head=head.next return k
练习题:
83. 删除排序链表中的重复元素 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ if head==None: return [] prev=head next_=head.next while next_: if prev.val==next_.val: prev.next=next_.next next_=next_.next continue prev=next_ next_=next_.next return head
876. 链表的中间结点 给定一个带有头结点 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 之间。 https://leetcode-cn.com/problems/middle-of-the-linked-list/
# 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 """ # 思路:先进行遍历其长度,下一步直接遍历其元素 first=head head_len=0 while first: head_len+=1 first=first.next head_2=head_len/2 first=head while head_2: head_2-=1 first=first.next return first
使用双指针解决链表问题提示 它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点： 1. 在调用 next 字段之前，始终检查节点是否为空。 获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。 2. 仔细定义循环的结束条件。 运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。 复杂度分析 空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 O(1)。但是，时间复杂度的分析比较困难。为了得到答案，我们需要分析运行循环的次数。 在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。 如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。 如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。 显然，M <= N 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 O(N)。 自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析，请考虑最糟糕的情况。