一个🤐哑结点解决链表问题
链表
链表（Linked List）是一种数据结构，用于存储一系列元素。每个元素由一个存储数据的节点（Node）和一个指向下一个元素的指针（Next）组成。通过这些指针，将一系列节点串起来形成链表，每个节点只能访问到它的下一个节点，不能随机访问其他节点。
链表有单向链表、双向链表和循环链表等类型。其中，单向链表每个节点只有一个指向下一个节点的指针，而双向链表每个节点有两个指针，分别指向前一个节点和后一个节点。循环链表则是一种特殊的链表，尾节点的指针指向头节点。
相对于数组，链表的优势在于可以高效地进行插入和删除操作，而无需移动其他元素。但链表的缺点是无法随机访问，访问某个节点的时间复杂度为 O(n)，因此不适用于需要随机访问的场景。
LeetCode 链表题目较为常见，是算法面试中经常考察的数据结构之一。链表是一种基本的数据结构，其优点是可以实现常数时间复杂度的插入和删除操作，而无需像数组一样进行大量的数据移动。
哑结点
哑结点（Dummy node） 通常是指在链表数据结构中使用的一个虚拟节点，它不包含任何实际的数据，仅用于协助链表操作的实现。
在链表的头部和尾部添加哑结点，可以使链表的操作更加简单高效。例如，当链表为空时，可以添加两个哑结点作为头部和尾部，这样就可以避免对空链表进行判断。在某些情况下，还可以使用哑结点来简化代码实现。
哑结点的实现方式有多种，例如可以使用一个空节点或者一个特定的数值来表示哑结点。具体实现方式可以根据具体的需求和代码设计进行选择。
相关题目
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 <= 100l1和l2均按 非递减顺序 排列
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
while list1 and list2:
if list1.val < list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
p.next = list1 if list1 else list2
return dummy.next
这段代码实现了合并两个有序链表的功能，时间复杂度为 O(n)O(n)O(n)，其中 nnn 是两个链表中较短的链表的长度，空间复杂度为 O(1)O(1)O(1)。
-
首先创建一个虚拟头结点
dummy，然后创建一个指针p指向dummy，用来拼接两个有序链表。 -
接下来遍历两个链表，如果链表
list1的当前节点的值小于链表list2的当前节点的值，则将p的下一个节点指向list1的当前节点，并将list1指向下一个节点。否则，将p的下一个节点指向list2的当前节点，并将list2指向下一个节点。 -
遍历完成后，如果还有链表
list1或list2中有剩余的节点，则直接将p的下一个节点指向剩余的节点即可。
最后返回虚拟头结点的下一个节点 dummy.next。
这个代码能AC但是不符合题意，因为题目要求不修改原来的链表并返回一个新的链表嗷。所以如果要按照题目写，空间复杂度为为O(m+n)O(m+n)O(m+n)
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [7,0,8]
解释： 342 + 465 = 807.
示例 2：
输入： l1 = [0], l2 = [0]
输出： [0]
示例 3：
输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出： [8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
vals = (v1 + v2 + carry) % 10
carry = (v1 + v2 + carry) // 10
p.next = ListNode(vals)
p = p.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
-
首先定义了一个哑结点dummy，作为新链表的头结点，并且定义了一个指针p，初始化为dummy。
-
定义了一个变量carry，表示进位的值，初始值为0。
-
进入循环，只要l1和l2中还有节点没有被遍历完，或者存在进位值，就继续循环。
-
对于每一位的相加，分别获取l1和l2的当前值（如果有的话），并且加上上一位的进位值，得到一个vals值，表示该位的和。
-
计算进位carry，根据vals的值是否大于等于10，如果大于等于10，就将carry设置为1，否则设置为0。
-
将vals的值插入新链表中，同时将指针p指向新链表的下一个节点，以便下一次插入。
-
将l1和l2的指针指向下一个节点，如果已经到了链表的末尾，就将指针设为None。
-
最后返回dummy.next，因为dummy是一个哑结点，所以实际上返回的是dummy的下一个节点，也就是新链表的头结点。
总体来说，这段代码的时间复杂度是O(max(m,n))，其中m和n分别是l1和l2的长度，因为需要遍历两个链表中的所有节点，以及可能的进位。空间复杂度是O(max(m,n))，因为需要创建一个新链表来存储结果。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n **个结点，并且返回链表的头结点。
示例 1：
输入： head = [1,2,3,4,5], n = 2
输出： [1,2,3,5]
示例 2：
输入： head = [1], n = 1
输出： []
示例 3：
输入： head = [1,2], n = 1
输出： [1]
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶： 你能尝试使用一趟扫描实现吗？
最容易想到的办法，两次遍历：
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 0
pir = head
while pir:
length += 1
pir = pir.next
dummy = ListNode(0,head)
cur = dummy
for i in range(0,length-n):
cur = cur.next
cur.next = cur.next.next
return dummy.next
下面是具体的分析：
-
首先定义了一个变量length表示链表的长度，初始化为0，并且定义了一个指针pir，初始化为head。
-
在while循环中，遍历链表中的每个节点，每经过一个节点，就将length加1，并将指针pir指向下一个节点。
-
定义了一个哑结点dummy，其值为0，其next指向head，这样可以避免对头结点进行特殊处理。
-
定义了一个指针cur，初始化为dummy。然后使用一个for循环，遍历链表中的前length-n个节点，将cur指向该节点。
-
然后将cur.next指向cur.next.next，就将倒数第n个节点从链表中删除了。
-
最后返回dummy.next，即为新链表的头结点。
总体来说，这段代码的时间复杂度为O(N)，其中N为链表的长度。因为需要遍历整个链表两次，空间复杂度为O(1)，因为只使用了常数个额外变量。
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
stack = []
p = dummy = ListNode(next = head)
while p:
stack.append(p)
p = p.next
for i in range(n+1):
q = stack.pop()
q.next = q.next.next
return dummy.next
该解决方案使用堆栈来跟踪链表中的节点，从头开始。然后，它从堆栈中弹出倒数第N个节点，并更新第（N+1）个节点的下一个指针以跳过第N个节点。
该解决方案使用一个虚拟节点作为链表的头节点，以简化对第一个节点的处理。
以下是该解决方案的逐步说明：
-
初始化一个堆栈和一个指向虚拟节点的指针
p。 -
遍历链表，将每个节点推入堆栈中。
-
遍历结束后，我们从堆栈中弹出N+1次，以获取倒数第N个节点之前的节点。
-
更新第（N+1）个节点的下一个指针以跳过第N个节点。
-
返回虚拟节点的下一个指针。
请注意，该解决方案的时间复杂度为O(n)，空间复杂度为O(n)，其中n是链表的长度。
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
fast = slow = dummy = ListNode(next=head)
for i in range(n):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
该解决方案使用两个指针fast和slow，同时从头开始遍历链表。指针fast首先移动n步，然后指针slow和fast以相同的速度移动，直到fast到达链表的末尾。此时，指针slow指向倒数第n个节点之前的节点。然后，我们更新指针slow的下一个指针以跳过第n个节点。
该解决方案使用一个虚拟节点作为链表的头节点，以简化对第一个节点的处理。
以下是该解决方案的逐步说明：
-
初始化两个指针
fast和slow，并将它们都指向虚拟节点。 -
将指针
fast向前移动n个节点。 -
同时移动指针
fast和slow，直到fast到达链表的末尾。 -
更新指针
slow的下一个指针以跳过第n个节点。 -
返回虚拟节点的下一个指针。
请注意，该解决方案的时间复杂度为O(n)，空间复杂度为O(1)，其中n是链表的长度。
61. 旋转链表
给你一个链表的头节点 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 <= 1000 <= k <= 2 * 109
常规做法：
class Solution:
def rotateRight(self, head, k):
if not head:
return
p = head
length = 1
while p.next:
length += 1
p = p.next
k %= length
dummy = ListNode()
q = head
for i in range(length - k - 1):
q = q.next
p.next = head
dummy.next = q.next
q.next = None
return dummy.next
首先遍历整个链表，获取链表长度 length，同时将尾节点 p 找出来。
将 k 对 length 取模，防止 k 大于链表长度。
设置 dummy 节点和指针 q 指向头节点，同时让 q 往前走 length-k-1 步，使其停留在旋转后的尾节点的前一个位置。这里需要注意 q 的起始位置是头节点，而不是 dummy 节点。
将尾节点 p 指向头节点，使整个链表形成一个环。
让 q.next = None，断开环，得到旋转后的单链表。
时间复杂度为 O(n)，其中 n 为链表长度。由于只使用了常数个额外空间，空间复杂度为 O(1)。
转化为环状链表 ：
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return
p = head
length = 1
while p.next:
length += 1
p = p.next
k %= length
p.next = head
for i in range(length - k):
p = p.next
head = p.next
p.next = None
return head
具体做法如下：
-
如果链表为空，则直接返回 None。
-
遍历整个链表，获取链表长度 length，并将尾节点 p 找出来。
-
将 k 对 length 取模，防止 k 大于链表长度。
-
将尾节点 p 的 next 指向头节点，使整个链表形成一个环。
-
再让 p 往前走 length - k 步，停留在旋转后的尾节点位置。
-
将头节点 head 指向 p 的 next，得到旋转后的单链表。
-
让 p.next = None，断开环，得到最终的结果。
该算法的时间复杂度为 O(n)，其中 n 为链表长度。由于只使用了常数个额外空间，空间复杂度为 O(1)。
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 **x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入： head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入： head = [2,1], x = 2
输出：[1,2]
提示：
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
class Solution:
def partition(self, head, x: int) :
small = dummy1 = ListNode()
big = dummy2 = ListNode()
while head:
if head.val < x:
small.next = head
head = head.next
small = small.next
small.next = None
else:
big.next = head
head = head.next
big = big.next
big.next = None
small.next = dummy2.next
return dummy1.next
这是一个Python类Solution，它有一个名为partition的方法，接受两个参数：head是一个链表，x是一个整数。该方法将链表分割成两个部分，所有节点值小于x的节点在所有节点值大于或等于x的节点之前。
该方法创建了两个虚拟节点dummy1和dummy2，分别作为两个单独链表的头部。然后，使用while循环迭代遍历原始链表中的每个节点，根据它的值是否小于x，将其附加到small或big链表中。
一旦所有节点都已被分配到small和big链表中，该方法将small链表中的最后一个节点的next指针设置为big链表中的第一个节点，并返回dummy1的next指针，即分割后的链表的头部。
请注意，该代码假设ListNode是一个表示链表中单个节点的类，并具有至少两个属性：val存储节点的值，next存储链表中下一个节点的引用。
时间复杂度：该方法使用一次遍历来分割原始链表，并在每次迭代中执行常量时间操作。因此，该算法的时间复杂度为O(n)，其中n是链表的长度。
空间复杂度：该方法使用了两个虚拟节点和两个指针来分割链表，因此空间复杂度为O(1)，与链表的长度无关。
82. 删除排序链表中的重复元素 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- 题目数据保证链表已经按升序 排列
class Solution:
def deleteDuplicates(self, head):
dummy = ListNode()
p = dummy
while head:
if head.next and head.next.val == head.val:
n = head.val
while head and head.val == n:
head = head.next
else:
p.next = head
head = head.next
p = p.next
p.next = None
return dummy.next
这是一个删除链表中重复元素的Python代码实现。该函数接受一个参数head，它是链表的头节点。函数返回删除重复元素后的链表头节点。
函数创建一个新的节点dummy作为新链表的头节点。它还创建一个指针p，指向新链表的最后一个节点。然后，它使用head指针遍历原始链表。
如果head.next存在且其值等于head.val，则函数进入一个循环，跳过所有与head具有相同值的节点。一旦循环完成，head指向与先前节点值不同的第一个节点。
如果head.next不存在或其值与head.val不同，则函数将head附加到由p指向的新链表，更新p以指向链表的新最后一个节点，并将p的next指针设置为None。
遍历完原始链表中的所有节点后，函数返回新链表的头节点，它是链表中的第二个节点，因为第一个节点是虚拟节点。
总体而言，这个实现的时间复杂度为O(n)，其中n是链表中节点的数量。空间复杂度为O(1)，因为函数只创建了常数数量的指针和节点。