18、删除链表的节点
问题描述：
难度：简单
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
代码部分
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def deleteNode(self, head: ListNode, val: int) -> ListNode: newHead = ListNode(0,head) newHead.next = head pre, curr = newHead,head while curr: if curr.val == val: pre.next = curr.next else: pre =curr curr = curr.next return newHead.next
22、链表中倒数第K个节点
问题描述
难度：简单
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
代码部分
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def getKthFromEnd(self, head: ListNode, k: int) -> ListNode: slow = head fast = head for _ in range(k): if fast == None: return fast fast = fast.next while fast: slow = slow.next fast = fast.next return slow
25、合并两个排序的链表
问题描述
难度：简单
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解题思路
利用归并排序的思想。
创建一个新的链表节点作为头节点（记得保存），然后判断 l1和 l2 头节点的值，将较小值的节点添加到新的链表中。
当一个节点添加到新的链表中之后，将对应的 l1 或 l2 链表向后移动一位。
然后继续判断当前 l1 节点和当前 l2 节点的值，继续将较小值的节点添加到新的链表中，然后将对应的链表向后移动一位。
这样，当 l1 或 l2 遍历到最后，最多有一个链表还有节点未遍历，则直接将该节点链接到新的链表尾部即可。
解题代码
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: newHead = ListNode(-1) curr = newHead while l1 and l2: if l1.val <l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next curr.next = l1 if l1 is not None else l2#当两个链表不相等的时候 return newHead.next
52、两个链表的第一个公共节点
问题描述
难度：简单
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 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
解题思路
如果两个链表相交，那么从相交位置开始，到结束，必有一段等长且相同的节点。假设链表 A 的长度为 m、链表 B 的长度为 n，他们的相交序列有 k 个，则相交情况可以如下如所示：
现在问题是如何找到 m-k 或者 n-k 的位置。
考虑将链表 A 的末尾拼接上链表 B，链表 B 的末尾拼接上链表 A。
然后使用两个指针 pA 、PB，分别从链表 A、链表 B 的头节点开始遍历，如果走到共同的节点，则返回该节点。
否则走到两个链表末尾，返回 None。
解题代码
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: if not headA or not headB: return None pA = headA pB = headB while pA != pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA
